循环矩阵

充分利用循环矩阵及其特性的是核相关滤波跟踪算法的另一个重要特征，它不仅涉及到目标采样，而且巧妙的将目标特征的频域空间与岭回归相结合，实现了目标特征的快速学习与检测。

首先考虑一维样本的情况，设x=[x0,x1,x2,⋯,xN−1]<script type="math/tex" id="MathJax-Element-1">{\bf{x}} = [{x_0},{x_1},{x_2}, \cdots ,{x_{N - 1}}]</script>表示一行图像像素样本，x<script type="math/tex" id="MathJax-Element-2">{\bf{x}}</script>的循环矩阵表示为：

<script type="math/tex; mode=display" id="MathJax-Element-3">{\bf{X}} = C({\bf{x}}) = \left[ {\matrix{ {{x_0}} & {{x_1}} & {{x_2}} & \cdots & {{x_{N - 1}}} \cr {{x_{N - 1}}} & {{x_0}} & {{x_1}} & \cdots & {{x_{N - 2}}} \cr {{x_{N - 2}}} & {{x_{N - 1}}} & {{x_0}} & \cdots & {{x_{N - 3}}} \cr \vdots & \vdots & \vdots & \ddots & \vdots \cr {{x_1}} & {{x_2}} & {{x_3}} & \cdots & {{x_0}} \cr } } \right]\tag{1}</script>
其中， x<script type="math/tex" id="MathJax-Element-4">\bf{x}</script>又称为X<script type="math/tex" id="MathJax-Element-5">\bf{X}</script>的生成向量。

循环矩阵有一个重要的性质为：任意循环矩阵均可以被离散傅立叶变换矩阵对角化，即：

<script type="math/tex; mode=display" id="MathJax-Element-6">{\bf{X}} = C({\bf{x}}) = {\bf{F}} \cdot diag\left( {{\cal F}({\bf{x}})} \right) \cdot {{\bf{F}}^{\rm{H}}}\tag{2}</script>
其中，F(⋅)<script type="math/tex" id="MathJax-Element-7">{\cal F}( \cdot )</script>表示离散傅立叶变换(Discrete Fourier Transform, DFT)，F<script type="math/tex" id="MathJax-Element-8">{\bf{F}}</script>表示DFT矩阵，具有如下形式：
<script type="math/tex; mode=display" id="MathJax-Element-9">{\bf{F}} = {1 \over {\sqrt n }}\left[ {\matrix{ 1 & 1 & 1 & \cdots & 1 \cr 1 & w & {{w^2}} & \cdots & {{w^{N - 1}}} \cr 1 & {{w^2}} & {{w^4}} & \cdots & {{w^{2(N - 1)}}} \cr \vdots & \vdots & \vdots & \ddots & \vdots \cr 1 & {{w^{N - 1}}} & {{w^{2(N - 1)}}} & \cdots & {{w^{{{(N - 1)}^2}}}} \cr } } \right]\tag{3}</script>
其中，w=e−j2π/N<script type="math/tex" id="MathJax-Element-10">w = e^{ - j{{2\pi}} /N}</script>为旋转因子，且F<script type="math/tex" id="MathJax-Element-11">{\bf{F}}</script>是一个酉矩阵，满足FHF=FFH=I<script type="math/tex" id="MathJax-Element-12">{{\bf{F}}^{\rm{H}}}{\bf{F}} = {\bf{F}}{{\bf{F}}^{\rm{H}}} = {\bf{I}}</script>。式(1)的证明过程见文献[49]. 通过式（2.7），以及F<script type="math/tex" id="MathJax-Element-13">{\bf{F}}</script>的性质，可以继续推导出循环矩阵具有以下特性：

1. 已知A,B<script type="math/tex" id="MathJax-Element-14">{\bf{A}},{\bf{B}}</script>都为循环矩阵，其生成向量分别是a,b<script type="math/tex" id="MathJax-Element-15">{\bf{a}},{\bf{b}}</script>，且具有相同的向量长度，则有以下公式成立：
   

   A+B=C(a+b)(4)
   <script type="math/tex; mode=display" id="MathJax-Element-16">{\bf{A}} + {\bf{B}} = C({\bf{a}} + {\bf{b}})\tag{4}</script>
   
   A⋅B=C(F−1(F(a)⊙F(b)))(5)
   <script type="math/tex; mode=display" id="MathJax-Element-17">{\bf{A}} \cdot {\bf{B}} = C\left( {{{\cal F}^{ - 1}}\left( {{\cal F}({\bf{a}}) \odot {\cal F}({\bf{b}})} \right)} \right)\tag{5}</script>
   其中F−1(⋅)<script type="math/tex" id="MathJax-Element-18">{{\cal F}^{ - 1}}( \cdot )</script>表离散傅立叶反变换(IDFT)，⊙<script type="math/tex" id="MathJax-Element-19"> \odot </script>表对位相乘运算。

   证明：
   

   A+B=F⋅diag(F(a))⋅FH+F⋅diag(F(b))⋅FH=F⋅diag(F(a)+F(b))⋅FH=C(F−1(F(a)+F(b)))=C(a+b)

   <script type="math/tex; mode=display" id="MathJax-Element-20">\displaylines{ {\bf{A}} + {\bf{B}} = {\bf{F}} \cdot diag\left( {{\cal F}({\bf{a}})} \right) \cdot {{\bf{F}}^{\rm{H}}} + {\bf{F}} \cdot diag\left( {{\cal F}({\bf{b}})} \right) \cdot {{\bf{F}}^{\rm{H}}} \cr = {\bf{F}} \cdot diag\left( {{\cal F}({\bf{a}}) + {\cal F}({\bf{b}})} \right) \cdot {{\bf{F}}^{\rm{H}}} \cr = C\left( {{{\cal F}^{ - 1}}\left( {{\cal F}({\bf{a}}) + {\cal F}({\bf{b}})} \right)} \right) \cr = C\left( {{\bf{a}} + {\bf{b}}} \right) \cr} </script>
   

   A⋅B=F⋅diag(F(a))⋅FH⋅F⋅diag(F(b))⋅FH=F⋅diag(F(a))⋅diag(F(b))⋅FH=F⋅diag(F(a)⊙F(b))⋅FH=C(F−1(F(a)⊙F(b)))

   <script type="math/tex; mode=display" id="MathJax-Element-21">\displaylines{ {\bf{A}} \cdot {\bf{B}} = {\bf{F}} \cdot diag\left( {{\cal F}({\bf{a}})} \right) \cdot {{\bf{F}}^{\rm{H}}} \cdot {\bf{F}} \cdot diag\left( {{\cal F}({\bf{b}})} \right) \cdot {{\bf{F}}^{\rm{H}}} \cr = {\bf{F}} \cdot diag\left( {{\cal F}({\bf{a}})} \right) \cdot diag\left( {{\cal F}({\bf{b}})} \right) \cdot {{\bf{F}}^{\rm{H}}} \cr = {\bf{F}} \cdot diag\left( {{\cal F}({\bf{a}}) \odot {\cal F}({\bf{b}})} \right) \cdot {{\bf{F}}^{\rm{H}}} \cr = C\left( {{{\cal F}^{ - 1}}\left( {{\cal F}({\bf{a}}) \odot {\cal F}({\bf{b}})} \right)} \right) \cr} </script>
   证毕

2. 已知X<script type="math/tex" id="MathJax-Element-22">{\bf{X}}</script>为循环矩阵，其生成向量为x<script type="math/tex" id="MathJax-Element-23">{\bf{x}}</script>，且向量元素为实数，则有以下公式成立：
   

   XT=F⋅diag(F∗(x))⋅FH(6)
   <script type="math/tex; mode=display" id="MathJax-Element-24">{{\bf{X}}^{\rm{T}}} = {\bf{F}} \cdot diag\left( {{{\cal F}^ * }({\bf{x}})} \right) \cdot {{\bf{F}}^{\rm{H}}}\tag{6}</script>
   
   X−1=F⋅diag(F(x))−1⋅FH(7)
   <script type="math/tex; mode=display" id="MathJax-Element-25">{{\bf{X}}^{ - 1}} = {\bf{F}} \cdot diag{\left( {{\cal F}({\bf{x}})} \right)^{ - 1}} \cdot {{\bf{F}}^{\rm{H}}}\tag{7}</script>

   证明：由于已知X<script type="math/tex" id="MathJax-Element-26">{\bf{X}}</script>为实矩阵，即X=X∗<script type="math/tex" id="MathJax-Element-27">{\bf{X}} = {{\bf{X}}^ * }</script>，且F<script type="math/tex" id="MathJax-Element-28">{\bf{F}}</script>为对称酉矩阵，则：
   

   XT=(F⋅diag(F(x))⋅FH)T=(FH)T⋅diag(F(x))⋅FT=F∗⋅diag(F(x))⋅FT=(F∗⋅diag(F(x))⋅FT)∗=F⋅diag(F∗(x))⋅FH

   <script type="math/tex; mode=display" id="MathJax-Element-29">\displaylines{ {{\bf{X}}^{\rm{T}}} = {\left( {{\bf{F}} \cdot diag\left( {{\cal F}({\bf{x}})} \right) \cdot {{\bf{F}}^H}} \right)^{\rm{T}}} \cr = {({{\bf{F}}^{\rm{H}}})^{\rm{T}}} \cdot diag\left( {{\cal F}({\bf{x}})} \right) \cdot {{\bf{F}}^{\rm{T}}} \cr = {{\bf{F}}^ * } \cdot diag\left( {{\cal F}({\bf{x}})} \right) \cdot {{\bf{F}}^{\rm{T}}} \cr = {\left( {{{\bf{F}}^ * } \cdot diag\left( {{\cal F}({\bf{x}})} \right) \cdot {{\bf{F}}^{\rm{T}}}} \right)^ * } \cr = {\bf{F}} \cdot diag\left( {{{\cal F}^ * }({\bf{x}})} \right) \cdot {{\bf{F}}^{\rm{H}}} \cr} </script>
   

   X−1=(F⋅diag(F(x))⋅FH)−1=(FH)−1⋅diag(F(x))−1⋅F−1=F⋅diag(F(x))−1⋅FH

   <script type="math/tex; mode=display" id="MathJax-Element-30">\displaylines{ {{\bf{X}}^{ - 1}} = {\left( {{\bf{F}} \cdot diag\left( {{\cal F}({\bf{x}})} \right) \cdot {{\bf{F}}^{\rm{H}}}} \right)^{ - 1}} \cr = {\left( {{{\bf{F}}^{\rm{H}}}} \right)^{ - 1}} \cdot diag{\left( {{\cal F}({\bf{x}})} \right)^{ - 1}} \cdot {{\bf{F}}^{ - 1}} \cr = {\bf{F}} \cdot diag{\left( {{\cal F}({\bf{x}})} \right)^{ - 1}} \cdot {{\bf{F}}^{\rm{H}}} \cr} </script>
   证毕

3. 已知X<script type="math/tex" id="MathJax-Element-31">{\bf{X}}</script>为循环矩阵，其生成向量为x<script type="math/tex" id="MathJax-Element-32">{\bf{x}}</script>，y<script type="math/tex" id="MathJax-Element-33">{\bf{y}}</script>为与x<script type="math/tex" id="MathJax-Element-34">{\bf{x}}</script>具有相同向量长度的向量，则有以下公式成立：
   

   F(Xy)=F∗(x)⊙F(y)(8)
   <script type="math/tex; mode=display" id="MathJax-Element-35">{\cal F}({\bf{Xy}}) = {{\cal F}^ * }({\bf{x}}) \odot {\cal F}({\bf{y}})\tag{8}</script>

   证明：
   

   Xy=C(x)y=⎡⎣⎢⎢⎢⎢⎢⎢⎢x0xN−1xN−2⋮x1x1x0xN−1⋮x2x2x1x0⋮x3⋯⋯⋯⋱⋯xN−1xN−2xN−3⋮x0⎤⎦⎥⎥⎥⎥⎥⎥⎥⎡⎣⎢⎢⎢⎢⎢⎢⎢y0y1y2⋮yN−1⎤⎦⎥⎥⎥⎥⎥⎥⎥

   <script type="math/tex; mode=display" id="MathJax-Element-36">{\bf{Xy}} = C({\bf{x}}){\bf{y}} = \left[ {\matrix{ {{x_0}} & {{x_1}} & {{x_2}} & \cdots & {{x_{N - 1}}} \cr {{x_{N - 1}}} & {{x_0}} & {{x_1}} & \cdots & {{x_{N - 2}}} \cr {{x_{N - 2}}} & {{x_{N - 1}}} & {{x_0}} & \cdots & {{x_{N - 3}}} \cr \vdots & \vdots & \vdots & \ddots & \vdots \cr {{x_1}} & {{x_2}} & {{x_3}} & \cdots & {{x_0}} \cr } } \right]\left[ {\matrix{ {{y_0}} \cr {{y_1}} \cr {{y_2}} \cr \vdots \cr {{y_{N - 1}}} \cr } } \right]</script>
   上式可以表示为向量x~=[x0,xN−1,xN−2,⋯,x1]T<script type="math/tex" id="MathJax-Element-37">{\bf{\tilde x}} = {[{x_0},{x_{N - 1}},{x_{N - 2}}, \cdots ,{x_1}]^{\rm{T}}}</script>与向量y<script type="math/tex" id="MathJax-Element-38">{\bf{y}}</script>的循环卷积，即：
   

   Xy=C(x)y=x~⊗y

   <script type="math/tex; mode=display" id="MathJax-Element-39">{\bf{Xy}} = C({\bf{x}}){\bf{y}} = {\bf{\tilde x}} \otimes {\bf{y}}</script>
   其中⊗<script type="math/tex" id="MathJax-Element-40"> \otimes </script>表示循环卷积。
   令Fx~y=F(x~⊗y)<script type="math/tex" id="MathJax-Element-41">{{\bf{F}}_{{\bf{\tilde xy}}}} = {\cal F}({\bf{\tilde x}} \otimes {\bf{y}})</script>，Fx~=F(x~)<script type="math/tex" id="MathJax-Element-42">{{\bf{F}}_{{\bf{\tilde x}}}} = {\cal F}({\bf{\tilde x}})</script>，Fy=F(y)<script type="math/tex" id="MathJax-Element-43">{{\bf{F}}_{\bf{y}}} = {\cal F}({\bf{y}})</script>，根据卷积定理，有

   Fx~y(n)=Fx~(n)⋅Fy(n)

   <script type="math/tex; mode=display" id="MathJax-Element-44">{{\bf{F}}_{{\bf{\tilde xy}}}}(n) = {{\bf{F}}_{{\bf{\tilde x}}}}(n) \cdot {{\bf{F}}_{\bf{y}}}(n)</script>
   即
   

   Fx~y=Fx~⊙Fy=F(x~)⊙F(y)

   <script type="math/tex; mode=display" id="MathJax-Element-45">{{\bf{F}}_{{\bf{\tilde xy}}}} = {{\bf{F}}_{{\bf{\tilde x}}}} \odot {{\bf{F}}_{\bf{y}}} = {\cal F}({\bf{\tilde x}}) \odot {\cal F}({\bf{y}})</script>
   根据DFT的定义，
   

   Fx~(u)=∑n=0N−1x~(n)wnu=x0w0+xN−1wu+xN−2w2u+⋯+x1w(N−1)u=x0w(N−N)u+x1w(N−1)u+x2w(N−2)u+⋯+xN−1wu=∑n=0N−1xnw(N−n)u

   <script type="math/tex; mode=display" id="MathJax-Element-46">\displaylines{ {{\bf{F}}_{{\bf{\tilde x}}}}(u) = \sum\limits_{n = 0}^{N - 1} {{\bf{\tilde x}}(n){w^{nu}}} \cr = {x_0}{w^0} + {x_{N - 1}}{w^u} + {x_{N - 2}}{w^{2u}} + \cdots + {x_1}{w^{(N - 1)u}} \cr = {x_0}{w^{(N - N)u}} + {x_1}{w^{(N - 1)u}} + {x_2}{w^{(N - 2)u}} + \cdots + {x_{N - 1}}{w^u} \cr = \sum\limits_{n = 0}^{N - 1} {{x_n}{w^{(N - n)u}}} \cr} </script>
   利用旋转因子w<script type="math/tex" id="MathJax-Element-47">w</script>的周期性，
   

   wN=e−j2πNN=1;w(N−n)u=wNu⋅w−nu=(wN)u⋅w−nu=w−nu

   <script type="math/tex; mode=display" id="MathJax-Element-48">\displaylines{ {w^N} = {e^{ - j{{2\pi } \over N}N}} = 1; \cr {w^{(N - n)u}} = {w^{Nu}} \cdot {w^{ - nu}} = {\left( {{w^N}} \right)^u} \cdot {w^{ - nu}} = {w^{ - nu}} \cr} </script>
   可得：
   

   Fx~(u)=∑n=0N−1xnw−nu

   <script type="math/tex; mode=display" id="MathJax-Element-49">{{\bf{F}}_{{\bf{\tilde x}}}}(u) = \sum\limits_{n = 0}^{N - 1} {{x_n}{w^{ - nu}}} </script>
   而向量x<script type="math/tex" id="MathJax-Element-50">{\bf{x}}</script>的DFT表达式为：
   

   Fx(u)=∑n=0N−1x(n)wnu=∑n=0N−1xnwnu

   <script type="math/tex; mode=display" id="MathJax-Element-51">{{\bf{F}}_{\bf{x}}}(u) = \sum\limits_{n = 0}^{N - 1} {{\bf{x}}(n){w^{nu}}} = \sum\limits_{n = 0}^{N - 1} {{x_n}{w^{nu}}} </script>
   可以发现，Fx~<script type="math/tex" id="MathJax-Element-52">{F_{{\bf{\tilde x}}}}</script>与Fx<script type="math/tex" id="MathJax-Element-53">{F_{\bf{x}}}</script>是互为共轭的关系，由此可得：
   

   F(Xy)=F(x~)⊙F(y)=F∗(x)⊙F(y)

   <script type="math/tex; mode=display" id="MathJax-Element-54">{\cal F}({\bf{Xy}}) = {\cal F}({\bf{\tilde x}}) \odot {\cal F}({\bf{y}}) = {{\cal F}^ * }({\bf{x}}) \odot {\cal F}({\bf{y}})</script>
   证毕

以上几条性质，对相关滤波器的证明非常重要。