  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.
