Near-Optimal Estimation of Simultaneously Sparse and Low-Rank Matrices from Nested Linear Measurements
Near-Optimal Estimation of Simultaneously Sparse and Low-Rank Matrices from Nested Linear Measurements
复制标题
来自嵌套线性测量的同时稀疏和低秩矩阵的近乎最优估计
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Romberg
中科院分区：
文献类型：
--
作者：
S. Bahmani;J. Romberg
本文考虑了从嵌套线性测量中同时估计低秩和逐行稀疏矩阵的问题，其中线性算子由线性算子$mathcal{W}$和矩阵$mathbf{varPsi}$的乘积组成。利用测量算子的嵌套结构，我们提出了一种计算效率高的两阶段算法来估计同时结构的目标矩阵。假设$mathcal{W}$是低秩矩阵的限制等距，$mathbf{varPsi}$是行向稀疏矩阵的限制等距，我们建立了对所有足够低秩和行向稀疏矩阵以高概率一致保持的精度保证。此外，利用信息论的标准工具，我们建立了从线性测量中同时估计低秩和行方向稀疏矩阵的极小极大下界，这些矩阵不需要嵌套。为该算法建立的精度边界，也可作为极大极小上界，与推导出的极大极小下界仅因维度的多对数因子而不同。因此，所提出的算法几乎是极小极大最优的。我们还讨论了所提出的观测模型的一些应用，并通过数值模拟对我们的算法进行了评价。
In this paper we consider the problem of estimating simultaneously low-rank and row-wise sparse matrices from nested linear measurements where the linear operator consists of the product of a linear operator $mathcal{W}$ and a matrix $mathbf{varPsi}$. Leveraging the nested structure of the measurement operator, we propose a computationally efficient two-stage algorithm for estimating the simultaneously structured target matrix. Assuming that $mathcal{W}$ is a restricted isometry for low-rank matrices and $mathbf{varPsi}$ is a restricted isometry for row-wise sparse matrices, we establish an accuracy guarantee that holds uniformly for all sufficiently low-rank and row-wise sparse matrices with high probability. Furthermore, using standard tools from information theory, we establish a minimax lower bound for estimation of simultaneously low-rank and row-wise sparse matrices from linear measurements that need not be nested. The accuracy bounds established for the algorithm, that also serve as a minimax upper bound, differ from the derived minimax lower bound merely by a polylogarithmic factor of the dimensions. Therefore, the proposed algorithm is nearly minimax optimal. We also discuss some applications of the proposed observation model and evaluate our algorithm through numerical simulation.
DOI：
--
发表时间：
2014-12
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Zhaoran Wang;Huanran Lu;Han Liu
通讯作者：
Zhaoran Wang;Huanran Lu;Han Liu
从傅里叶测量中快速检索压缩相位
DOI：
10.1109/icassp.2015.7178575
发表时间：
2015
期刊：
2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
影响因子：
--
作者：
C. Yapar;V. Pohl;P. Boche
通讯作者：
P. Boche