Matrix sensing is a problem in signal processing and machine learning that involves recovering a low-rank matrix from a set of linear measurements. The goal is to reconstruct the original matrix as accurately as possible, given only a set of linear measurements obtained by sensing the matrix [Jain, Netrapalli and Shanghavi, 2013]. In this work, we focus on a particular direction of matrix sensing, which is called rank-$1$ matrix sensing [Zhong, Jain and Dhillon, 2015]. We present an improvement over the original algorithm in [Zhong, Jain and Dhillon, 2015]. It is based on a novel analysis and sketching technique that enables faster convergence rates and better accuracy in recovering low-rank matrices. The algorithm focuses on developing a theoretical understanding of the matrix sensing problem and establishing its advantages over previous methods. The proposed sketching technique allows for efficiently extracting relevant information from the linear measurements, making the algorithm computationally efficient and scalable. Our novel matrix sensing algorithm improves former result [Zhong, Jain and Dhillon, 2015] on in two senses: $\bullet$ We improve the sample complexity from $\widetilde{O}(\epsilon^{-2} dk^2)$ to $\widetilde{O}(\epsilon^{-2} (d+k^2))$. $\bullet$ We improve the running time from $\widetilde{O}(md^2 k^2)$ to $\widetilde{O}(m d^2 k)$. The proposed algorithm has theoretical guarantees and is analyzed to provide insights into the underlying structure of low-rank matrices and the nature of the linear measurements used in the recovery process. It advances the theoretical understanding of matrix sensing and provides a new approach for solving this important problem.
翻译:信号处理和机器学习是信号处理和机器学习中的一个问题,涉及到从一组线性测量中恢复一个低位矩阵。目标是尽可能准确地重建原始矩阵,只考虑到通过感测矩阵[Jain、Netrapalli和Shanghavi,2013年]而获得的一系列线性测量。在这项工作中,我们侧重于一个特定的矩阵遥感方向,即排名-1美元[Zhong、Jain和Dhillon,2015年]。我们展示了与[Zhong、Jain和Dhillon,2015年]的原始算法相比的改进。它基于一种新的分析和草图技术,在恢复低位矩阵时能够实现更快的趋同率和准确性测量。算法侧重于从理论上了解矩阵感测问题并确定其比以往方法的优势。拟议的绘图技术可以高效地从线性测量中提取相关信息,使算法的效率和可缩放量。我们的新矩阵测算法改进了[Zhong, Jain和Dhillon,2015年]的原算法,它基于两个意义上: $(Bull2)我们改进了从基值的直线性直向全局的直径直径直径解,从$=O_O\\\xxxxxxxxxx。</s>