Timezone: »

 
Poster
Fast recovery from a union of subspaces
Chinmay Hegde · Piotr Indyk · Ludwig Schmidt

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #124
in Wednesday Posters »

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.

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

Author Information

Chinmay Hegde (New York University)
Piotr Indyk (MIT)
Ludwig Schmidt (MIT)

More from the Same Authors