Matrix sensing has many real-world applications in science and engineering, such as system control, distance embedding, and computer vision. The goal of matrix sensing is to recover a matrix $A_\star \in \mathbb{R}^{n \times n}$, based on a sequence of measurements $(u_i,b_i) \in \mathbb{R}^{n} \times \mathbb{R}$ such that $u_i^\top A_\star u_i = b_i$. Previous work [ZJD15] focused on the scenario where matrix $A_{\star}$ has a small rank, e.g. rank-$k$. Their analysis heavily relies on the RIP assumption, making it unclear how to generalize to high-rank matrices. In this paper, we relax that rank-$k$ assumption and solve a much more general matrix sensing problem. Given an accuracy parameter $\delta \in (0,1)$, we can compute $A \in \mathbb{R}^{n \times n}$ in $\widetilde{O}(m^{3/2} n^2 \delta^{-1} )$, such that $ |u_i^\top A u_i - b_i| \leq \delta$ for all $i \in [m]$. We design an efficient algorithm with provable convergence guarantees using stochastic gradient descent for this problem.
翻译：求解秩一矩阵感知的通用算法
翻译后的摘要：
矩阵感知在科学和工程的许多实际应用中非常重要，例如系统控制、距离嵌入和计算机视觉等领域。矩阵感知的目标是基于一系列的测量$(u_i,b_i)\in \mathbb{R}^{n}\times\mathbb{R}$来恢复矩阵$A_{\star}\in \mathbb{R}^{n\times n}$，使得$u_{i}^{T}A_{\star}u_{i}=b_{i}$。之前的研究(ZJD15)侧重于矩阵$A_{\star}$具有小秩，例如秩为$k$的情况。他们的分析非常依赖于RIP假设，这使得如何推广到高秩矩阵变得不清楚。本文放松了秩为$k$的假设，并解决了一个更加普遍的矩阵感知问题。给定精度参数$\delta\in(0,1)$，我们可以计算出$A\in \mathbb{R}^{n\times n}$，其复杂度为$\widetilde{O}(m^{3/2}n^{2}\delta^{-1})$，满足对于所有$i\in[m]$，都有$|u_{i}^{T}A u_{i}-b_{i}|\leq\delta$。我们设计了一个使用随机梯度下降的有效算法，具有可证的收敛性保证。
相关内容
微信扫码咨询专知VIP会员