Short-Flat Decompositions and Faster Algorithms for Linear Inverse Problems
summary
Introduces short-flat decompositions as the structural tool that lets projected gradient methods tolerate a semi-random adversary and still recover sparse signals in near-linear time under RIP-design matrices, with an SD-like runtime that interpolates to s·d when many rows are random. For matrix completion the method uses ~d r samples and roughly r^2 time to recover a rank-r matrix up to O(δ) error on ~99% of rows/columns (then boosts to full recovery under a regular-subspace or incoherence assumption), via L1 projection, weighted row reweighting, and SGD for the weights.
AI-written summary · about