论文标题
使用消息传递来绘制稀疏的低级矩阵，并使用消息传递近乎最佳的样本和时间复杂性
Sketching sparse low-rank matrices with near-optimal sample- and time-complexity using message passing
论文作者
论文摘要
我们考虑从少量线性测量值（草图）中恢复$ n_1 \ times n_2 $低率矩阵的问题。我们提出了一种素描方案和一种算法，该算法可以以很高的概率恢复单数向量，样品复杂性和运行时间仅取决于$ k $，而不取决于$ n_1 $和$ n_2 $。我们的素描操作员基于Li等人的压缩传感方案。 Bakshi等人使用了稀疏平价检查矩阵和部分DFT矩阵的组合。我们的主要贡献是对两阶段迭代算法的设计和分析，该算法通过利用矩阵的同时稀疏且低级别的结构来恢复奇异向量。我们根据精确恢复的概率得出了一个非互闭性绑定，该恢复的可能性适用于任何$ n_1 \ times n_2 $稀疏，低级矩阵。我们还展示了如何适应该方案以应对大约稀疏和低级别的矩阵。理论结果通过数值模拟和与现有方案的比较来验证，这些方案使用凸编程进行恢复。
We consider the problem of recovering an $n_1 \times n_2$ low-rank matrix with $k$-sparse singular vectors from a small number of linear measurements (sketch). We propose a sketching scheme and an algorithm that can recover the singular vectors with high probability, with a sample complexity and running time that both depend only on $k$ and not on the ambient dimensions $n_1$ and $n_2$. Our sketching operator, based on a scheme for compressed sensing by Li et al. and Bakshi et al., uses a combination of a sparse parity check matrix and a partial DFT matrix. Our main contribution is the design and analysis of a two-stage iterative algorithm which recovers the singular vectors by exploiting the simultaneously sparse and low-rank structure of the matrix. We derive a nonasymptotic bound on the probability of exact recovery, which holds for any $n_1\times n_2 $ sparse, low-rank matrix. We also show how the scheme can be adapted to tackle matrices that are approximately sparse and low-rank. The theoretical results are validated by numerical simulations and comparisons with existing schemes that use convex programming for recovery.
