Optimal Convex Lifted Sparse Phase Retrieval and PCA With an Atomic Matrix Norm Regularizer
Optimal Convex Lifted Sparse Phase Retrieval and PCA With an Atomic Matrix Norm Regularizer
复制标题
DOI：
10.1109/tit.2022.3228508
复制
发表时间：
2021-11
影响因子：
2.5
通讯作者：
Andrew D. McRae;J. Romberg;M. Davenport
中科院分区：
文献类型：
--
作者：
Andrew D. McRae;J. Romberg;M. Davenport
我们提出了新的分析和算法，解决稀疏相位恢复和稀疏主成分分析（PCA）与凸提升矩阵配方。关键的创新是一个新的混合原子矩阵范数，当用作正则化时，促进了具有稀疏因子的低秩矩阵。我们表明，凸计划与此原子规范作为正则化提供了接近最佳的样本复杂性和错误率保证稀疏相位检索和稀疏PCA。虽然我们不知道如何解决凸规划准确的有效算法，相位检索的情况下，我们仔细分析的程序和它的对偶，从而得出一个实用的启发式算法。我们的经验表明，这种实用的算法执行类似于现有的最先进的算法。
We present novel analysis and algorithms for solving sparse phase retrieval and sparse principal component analysis (PCA) with convex lifted matrix formulations. The key innovation is a new mixed atomic matrix norm that, when used as regularization, promotes low-rank matrices with sparse factors. We show that convex programs with this atomic norm as a regularizer provide near-optimal sample complexity and error rate guarantees for sparse phase retrieval and sparse PCA. While we do not know how to solve the convex programs exactly with an efficient algorithm, for the phase retrieval case we carefully analyze the program and its dual and thereby derive a practical heuristic algorithm. We show empirically that this practical algorithm performs similarly to existing state-of-the-art algorithms.