Fast recovery from a union of subspaces
Fast recovery from a union of subspaces
复制标题
从子空间并集快速恢复
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ludwig Schmidt
中科院分区：
文献类型：
--
作者：
C. Hegde;P. Indyk;Ludwig Schmidt
我们解决了在一般情况下从线性观测中恢复高维但结构化向量的问题，其中向量可以来自子空间的任意并集。这一设置包含了很多研究过的问题，比如压缩感知和低秩矩阵恢复。我们展示了如何使用*近似*投影设计更有效的子空间恢复问题的并集算法。实例化我们的低秩矩阵恢复问题的一般框架，给出了具有最佳样本复杂度的算法的最快可证明运行时间。此外，我们给出了二维直方图的快速近似投影，这是另一种研究得很好的低维数据模型。我们补充了我们的理论结果与实验表明，我们的框架也导致改进的时间和样本的复杂性经验。
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.