A General Algorithm for Solving Rank-one Matrix Sensing
share
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_⋆∈ℝ^n × n, based on a sequence of measurements (u_i,b_i) ∈ℝ^n×ℝ such that u_i^⊤ A_⋆ u_i = b_i. Previous work [ZJD15] focused on the scenario where matrix A_⋆ 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 δ∈ (0,1), we can compute A ∈ℝ^n × n in O(m^3/2 n^2 δ^-1 ), such that |u_i^⊤ A u_i - b_i| ≤δ for all i ∈ [m]. We design an efficient algorithm with provable convergence guarantees using stochastic gradient descent for this problem.
READ FULL TEXT