On Convergence of the Alternating Projection Method for Matrix Completion and Sparse Recovery Problems

2017/11/06 by Ming‐Jun Lai, Ming Jun Lai, Lai, Ming Jun +2
Computer Science · Engineering · Mathematics · #Blind Source Separation Techniques #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.1711.02151

29

arxiv created 2017/11/06 · openalex publication_date 2017/11/06 · arxiv updated 2017/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we study the convergence of Alternating Projection (AP) algorithm for the matrix completion and compressed sensing problems. We also present computational evidence for the excellent performance of the algorithm. Also, in the last section, we prove using algebraic-geometric techniques that, fixing the known positions, if a rank r matrix can be completed in finitely many ways using one given set of known entries, then, for almost all set of known entries, the matrix can be only completed into a rank r matrix in finitely many ways.

Citations

• Atomic Decomposition by Basis Pursuit
• Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0<q⩽1
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Iteratively reweighted least squares minimization for sparse recovery
• A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems
• Iterative hard thresholding for compressed sensing

Related

• Convergence of the Generalized Alternating Projection Algorithm for Compressive Sensing
• An inexact alternating projection method with application to matrix completion
• Weighted algorithms for compressed sensing and matrix completion
• Survey of Matrix Completion Algorithms
• Low-rank Matrix Completion using Alternating Minimization