Nearly Instance Optimal Sparse Matrix Approximation from Matrix-Vector Products

Christoper Musco, Indu Ramesh

A large body of work studies the problem of learning an approximation to an implicit matrix $A\in {\mathbb{R}}^{m\times n}$ that is only accessible implicitly via matrix-vector produ…