Typical l1-reconstruction limit of sparse vectors represented by concatenations of random orthogonal matrices
Typical l1-reconstruction limit of sparse vectors represented by concatenations of random orthogonal matrices
复制标题
由随机正交矩阵串联表示的稀疏向量的典型 l1 重建极限
DOI：
10.1088/1742-5468/2012/12/p12003
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Mikko Vehkaperae and Saikat Chatterjee
中科院分区：
文献类型：
--
作者：
Yoshiyuki Kabashima;Mikko Vehkaperae and Saikat Chatterjee
我们考虑从 M (< N) 维的线性变换 y= Dx 恢复 N 维稀疏向量 x 的问题。在约束 y= Dx 下 x 的 l 1-范数的最小化是恢复问题的标准方法，早期的研究报告称，通常成功的 l 1-恢复的关键条件在各种随机构造的矩阵 D 上是通用的。为了检查通用性的程度，我们重点关注通过连接根据 Haar 度量均匀绘制的 T= N/M 矩阵 O 1, O 2,..., O T 来提供 D 的情况。米×米 正交矩阵。通过使用复制方法并结合积分公式的发展来处理随机正交矩阵，我们表明当 T 矩阵模块中非零信号的密度不均匀时，级联矩阵可以比普适性预测的恢复性能更好。对于均匀非零信号密度的特殊情况再现了通用条件。大量的数值实验支持了理论预测。
We consider the problem of recovering an N-dimensional sparse vector x from its linear transformation y= Dx of M (< N) dimensions. Minimization of the l 1-norm of x under the constraint y= Dx is a standard approach for the recovery problem, and earlier studies report that the critical condition for typically successful l 1-recovery is universal over a variety of randomly constructed matrices D. To examine the extent of the universality, we focus on the case in which D is provided by concatenating T= N/M matrices O 1, O 2,..., O T drawn uniformly according to the Haar measure on the M× M orthogonal matrices. By using the replica method in conjunction with the development of an integral formula to handle the random orthogonal matrices, we show that the concatenated matrices can result in better recovery performance than that predicted by the universality when the density of non-zero signals is not uniform among the T matrix modules. The universal condition is reproduced for the special case of uniform non-zero signal densities. Extensive numerical experiments support the theoretical predictions.