Fast recovery from a union of subspaces

Chinmay Hegde, Piotr Indyk, Ludwig Schmidt

    Research output: Contribution to journalConference articlepeer-review


    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.

    Original languageEnglish (US)
    Pages (from-to)4401-4409
    Number of pages9
    JournalAdvances in Neural Information Processing Systems
    StatePublished - 2016
    Event30th Annual Conference on Neural Information Processing Systems, NIPS 2016 - Barcelona, Spain
    Duration: Dec 5 2016Dec 10 2016

    ASJC Scopus subject areas

    • Computer Networks and Communications
    • Information Systems
    • Signal Processing


    Dive into the research topics of 'Fast recovery from a union of subspaces'. Together they form a unique fingerprint.

    Cite this