Skip to yearly menu bar Skip to main content


Fast recovery from a union of subspaces

Chinmay Hegde · Piotr Indyk · Ludwig Schmidt

Area 5+6+7+8 #124

Keywords: [ Sparsity and Feature Selection ] [ (Other) Regression ] [ (Other) Optimization ] [ Learning Theory ]


We address the problem of recovering a high-dimensional but structured vector from linear observations in a general setting where the vector can come from an arbitrary union of subspaces. This setup includes well-studied problems such as compressive sensing and low-rank matrix recovery. We show how to design more efficient algorithms for the union-of subspace recovery problem by using approximate projections. Instantiating our general framework for the low-rank matrix recovery problem gives the fastest provable running time for an algorithm with optimal sample complexity. Moreover, we give fast approximate projections for 2D histograms, another well-studied low-dimensional model of data. We complement our theoretical results with experiments demonstrating that our framework also leads to improved time and sample complexity empirically.

Live content is unavailable. Log in and register to view live content