基于QR分解的等角紧框架完备化方法

《Mathematics》：Completion of Equiangular Tight Frames via QR Decomposition

　　

本文给出了一个众所周知的结论的构造性证明：?n中n+1个向量的每个等角紧框架（Equiangular Tight Frame，ETF）等于标准Mercedes-Benz（MB）框架的带符号正交变换，通过QR分解建立了?n中n+1个向量的等角紧框架与标准MB框架之间的显式关系。该关系被用于发展一种基于QR的方法，用以替换?n中n+1个向量的等角紧框架中缺失的向量，从而完备化一个等角紧框架。本文还给出了?n中标准MB框架元素的简单递推关系和显式表达式。文中提供了一个?5中的算例以演示该方法。对随机生成问题的初步数值试验表明，该方法准确且稳定。

基于QR分解的等角紧框架完备化：理论、算法与数值验证

一、研究背景与问题提出

有限紧框架（tight frame）在信号处理、编码理论、压缩感知等领域具有广泛的应用价值。对于具有给定范数的有限紧框架，Casazza等人[1,2]建立了其存在性的基本不等式：对于正整数m≥n及满足a₁≥a₂≥…≥a_m>0的实数序列，存在第i列长度为a_i的紧框架矩阵当且仅当该基本不等式成立。

在实际应用中，经常遇到框架元素部分缺失的问题，即需要从已知的部分框架元素出发，构造缺失的向量以完备化整个框架。已有研究包括：基于奇异值分解（Singular Value Decomposition，SVD）的方法用于完备化等范数紧框架[3]，以及基于QR分解的方法用于借助所谓标准MB矩阵S完备化部分Mercedes-Benz（MB）框架[4]。

本文旨在将先前针对MB框架的结果推广到更一般的等角紧框架（Equiangular Tight Frame，ETF）。具体而言，当?ⁿ中n+1个向量的等角紧框架的某些元素缺失时，可利用QR分解完备化该等角紧框架，从而为构造包含某些指定框架元素的等角紧框架提供方法。这一目标的实现依赖于一个众所周知的事实：?ⁿ中n+1个等角单位向量的集合等价于标准MB框架的带符号正交变换（参见文献[5]的(6.12)式）。

二、研究内容与主要结论

研究人员首先通过QR分解给出了这一经典结果的构造性证明，将ETF矩阵F表示为F=QDS的形式，其中Q为正交矩阵，D为对角线元素为1或?1的对角矩阵。随后，建立了所有容许完备化的显式表达式，并基于该表达式发展了计算方法：当?ⁿ中n+1个向量的等角紧框架的部分向量缺失时，通过计算替代向量来完备化框架。当该方法应用于部分MB框架时，可退化为文献中的既有方法。此外，该方法可通过闭式完备化表达式(26)直接推广以生成所有容许的完备化。

三、关键技术方法

本文采用的主要技术方法包括：

1. 1.
   QR分解：对部分等角紧框架矩阵F进行QR分解（F=QR），利用上三角矩阵R的结构提取关键信息；
2. 2.
   标准MB框架矩阵S的构造：通过简单递推关系(7)或显式表达式(14)(15)计算S的元素，进而构造S的列向量；
3. 3.
   带符号正交变换：利用定理1中F=QDS的刻画，将部分ETF与标准MB框架建立联系；
4. 4.
   闭式完备化公式：基于定理2建立完备化公式(26)，通过计算H=Q₁D₁B₂得到缺失向量的替代。

四、研究结果

4.1 预备性质（第2节）

引理1：给定?ⁿ中m个向量，若满足|?f_i,f_j?|=1/n（i≠j）且‖f_i‖=1，则当m≤n+1时，f₁,…,f_m线性无关。证明利用严格对角占优矩阵的非奇异性。

命题1：对MB框架的Gram矩阵G进行QR分解，可提取出上三角MB框架矩阵，即标准MB框架矩阵S。

引理2：标准MB框架矩阵S的元素满足递推关系(7)，其中α_i和β_i由初始值α₁=1、β₁=?1/(n+1)唯一确定，S的列向量由(8)式给出。

引理3：S的列向量可由显式表达式(14)和(15)直接计算α_i和β_i，无需递推。

定理1：F是?ⁿ的等角紧框架当且仅当存在正交矩阵Q和对角矩阵D（对角线元素为±1）使得F=QDS。该定理通过QR分解给出了构造性证明，与文献[5]的(6.12)式不同之处在于D的(n+1,n+1)元素取为1。

4.2 完备化结果（第3节）

引理4：设F为?ⁿ中n+1个向量的等角紧框架中m个给定向量构成的矩阵，F=QR为其正对角线元素的QR分解，则R的第一行形式为(1,1/n,…,1/n)。

定理2：设F为m个给定向量构成的矩阵，R₁为R的前m行子矩阵，B₂为S的最后n+1?m列子矩阵，D₁为由引理4定义的n×n对角矩阵，则H的列可添加到给定集合中以构成?ⁿ的等角紧框架当且仅当H具有形式(26)，即H=Q₁D₁B₂。

算法1：给出了完备化部分ETF的具体计算步骤：(i)对F进行QR分解；(ii)通过递推(7)或显式表达式(14)(15)构造标准MB框架矩阵S并取其后n+1?m列构成B₂；(iii)取D₁=I，按(26)计算H，返回H的列向量作为完备化结果。

算例1：在?⁵中给定三个单位向量，通过所提方法构造了缺失的三个替代向量，计算误差‖X^TX?I‖和‖X^TX?(6/5)I‖均达到很高精度。

数值试验：对随机生成的多种规模（n和k的10种组合）各20个测试问题，平均误差记录于表1；对算例1及随机测试问题引入范数相对扰动，平均误差记录于表2，表明算法准确且稳定。

五、讨论与结论

讨论部分：当等角紧框架中少量向量缺失时，定理2表明存在2^n+1?m种可能的扩展方式，其中必有一种为原始框架。所提方法取D₁=I，返回一个有效的ETF完备化，但通常不是原始框架。当原始框架为MB框架时，d_i=1对所有i成立，方法退化为文献[4]中的方法。通过选择定理2中D₁的其他容许取值，可获得其他完备化；若需获得所有容许完备化，可在算法1步骤(iii)中遍历D₁的所有容许选择。

结论部分：本文通过QR分解给出了?ⁿ中n+1个向量的等角紧框架与标准MB框架之间等价关系的构造性证明，建立了完备化的闭式表达式，发展了基于QR分解的完备化方法，并通过算例和随机数值试验验证了方法的准确性和稳定性。