2020/01/11 by Marcia Fampa, Fampa, Marcia, Jon Lee +5 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2001.03732
openalex publication_date 2020/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The well-known M-P (Moore-Penrose) pseudoinverse is used in several linear-algebra applications; for example, to compute least-squares solutions of inconsistent systems of linear equations. Irrespective of whether a given matrix is sparse, its M-P pseudoinverse can be completely dense, potentially leading to high computational burden and numerical difficulties, especially when we are dealing with high-dimensional matrices. The M-P pseudoinverse is uniquely characterized by four properties, but not all of them need to be satisfied for some applications. In this context, Fampa and Lee (Oper. Res. Letters, 46:605--610, 2018) and Xu, Fampa, Lee and Ponte (SIAM J. on Optimization, to appear) propose local-search procedures to construct sparse block-structured generalized inverses that satisfy only some of the M-P properties. (Vector) 1-norm minimization is used to induce sparsity and to keep the magnitude of the entries under control, and theoretical results limit the distance between the 1-norm of the solution of the local searches and the minimum 1-norm of generalized inverses with corresponding properties. We have implemented several local-search procedures based on results presented in these two papers and make here an experimental analysis of them, considering their application to randomly generated matrices of varied dimensions, ranks, and densities. Further, we carried out a case study on a real-world data set.