论文标题
低级别的压缩感应加上稀疏矩阵
Compressed sensing of low-rank plus sparse matrices
论文作者
论文摘要
表达矩阵作为低级矩阵加上稀疏矩阵的总和是一种灵活的模型，该模型捕获了鲁棒性PCA的数据中的全球和局部特征（Candes等，2011; Chandrasekaran等，2009）。压缩传感，矩阵完成及其变体（Eldar和Kutyniok，2012; Foucart and Rauhut，2013）已经确定，满足低复杂度模型的数据可以有效地测量并从与模型复杂性成比例的许多测量值中恢复，而不是环境增长。该手稿的制定保证表明，$ m \ times n $矩阵可以用$ r $矩阵和$ s $ r $矩阵和a $ s -s-sparse矩阵的总和可以通过计算上可拖动的方法从$ \ mathcal {o}（r（m+n-r）+n-r）+log（m+n-r）\ log（mn）\ log（mn/s $ linear s）恢复。 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 $μ<\sqrt{mn}/(r\sqrt{s})$, and subsequently, the restricted isometry constants for the aforementioned matrices remain bounded independent of problem size provided $p/mn$, $s/p$, and $ R（M+N-R）/P $保持固定。此外，我们表明半决赛编程和两个硬阈值梯度下降算法，NIHT和NAHT，只要测量操作员的RIC足够小，就会收敛到测量的矩阵。 These results also provably solve convex and non-convex formulation of Robust PCA with the asymptotically optimal fraction of corruptions $α=\mathcal{O}\left(1/(μr) \right)$, where $s = α^2 mn$, and improve the previously best known guarantees by not requiring that the fraction of corruptions is spread in every column and row by being upper bounded by $α$.显示了这些结果的数值实验，显示了用于合成问题，动态前景/静态背景分离和多光谱成像的数值实验。
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 popularized as Robust PCA (Candes et al., 2011; Chandrasekaran et al., 2009). Compressed sensing, matrix completion, and their variants (Eldar and Kutyniok, 2012; Foucart and Rauhut, 2013) 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\times 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 $\mathcal{O}(r(m+n-r)+s)\log(mn/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 $μ<\sqrt{mn}/(r\sqrt{s})$, and subsequently, the restricted isometry constants for the aforementioned matrices remain bounded independent of problem size provided $p/mn$, $s/p$, and $r(m+n-r)/p$ remain fixed. Additionally, we show that semidefinite programming and two hard threshold gradient descent algorithms, NIHT and NAHT, converge to the measured matrix provided the measurement operator's RIC's are sufficiently small. These results also provably solve convex and non-convex formulation of Robust PCA with the asymptotically optimal fraction of corruptions $α=\mathcal{O}\left(1/(μr) \right)$, where $s = α^2 mn$, and improve the previously best known guarantees by not requiring that the fraction of corruptions is spread in every column and row by being upper bounded by $α$. Numerical experiments illustrating these results are shown for synthetic problems, dynamic-foreground/static-background separation, and multispectral imaging.
