Compressed sensing of low-rank plus sparse matrices
Compressed sensing of low-rank plus sparse matrices
复制标题
DOI：
10.1016/j.acha.2023.01.008
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Jared Tanner;Simon Vary
中科院分区：
文献类型：
--
作者：
Jared Tanner;Simon Vary
将矩阵表示为低秩矩阵加上稀疏矩阵的和是一种灵活的模型，可以捕获数据中的全局和局部特征。该模型是鲁棒主元分析[1]、[2]的基础，并被动态前景/静态背景分离[3]推广。压缩感知、矩阵补全及其变体[4]、[5]已经确定，满足低复杂度模型的数据可以有效地测量，并从与模型复杂度而不是环境维度成比例的多个测量中恢复。这篇手稿发展了类似的保证，表明可以表示为秩-r矩阵和s-稀疏矩阵之和的m× n矩阵可以通过计算上易于处理的方法从O（r（m+ n− r）+ s）log n（m n/s）线性测量恢复。更具体地说，我们建立了低秩加稀疏矩阵集是封闭的，只要低秩分量的不相干性是上界μ< m n/（r s），并且随后，上述矩阵的受限等距常数保持有界，与问题大小无关，只要p/m n，s/p和r（m+ n− r）/p保持固定。此外，我们表明，半定规划和两个非凸硬阈值梯度下降算法，NIHT和NAHT，收敛到测量矩阵的测量算子的RIC是足够小的。这些结果也可证明地解决了鲁棒主成分分析的凸公式，其中渐近最优的腐败分数α= O（1/（μ r）），其中s= α 2 m n，并通过不要求腐败分数在每一列和行中传播而改进了先前已知的保证。数值实验表明，这些结果的合成问题，动态前景/静态背景分离，和多光谱成像。
Expressing a matrix as the sum of a low-rank matrix plus a sparse matrix is a flexible model capturing global and local features in data. This model is the foundation of robust principle component analysis [1],[2], and popularized by dynamic-foreground/static-background separation [3]. Compressed sensing, matrix completion, and their variants [4],[5] have established that data satisfying low complexity models can be efficiently measured and recovered from a number of measurements proportional to the model complexity rather than the ambient dimension. This manuscript develops similar guarantees showing that m× n matrices that can be expressed as the sum of a rank-r matrix and a s-sparse matrix can be recovered by computationally tractable methods from O (r (m+ n− r)+ s) log(m n/s) linear measurements. More specifically, we establish that the low-rank plus sparse matrix set is closed provided the incoherence of the low-rank component is upper bounded as μ< m n/(r s), and subsequently, the restricted isometry constants for the aforementioned matrices remain bounded independent of problem size provided p/m n, s/p, and r (m+ n− r)/p remain fixed. Additionally, we show that semidefinite programming and two non-convex hard threshold gradient descent algorithms, NIHT and NAHT, converge to the measured matrix provided the measurement operator's RICs are sufficiently small. These results also provably solve the convex formulation of Robust PCA with the asymptotically optimal fraction of corruptions α= O (1/(μ r)), where s= α 2 m n, and improve the previously known guarantees by not requiring that the fraction of corruptions is spread in every column and row by being upper bounded with α. Numerical experiments illustrating these results are shown for synthetic problems, dynamic-foreground/static-background separation, and multispectral imaging.