Experimental analysis of local searches for sparse reflexive generalized inverses

Marcia Fampa (), Jon Lee (), Gabriel Ponte () and Luze Xu ()
Additional contact information
Marcia Fampa: Federal University of Rio de Janeiro
Jon Lee: University of Michigan
Gabriel Ponte: Federal University of Rio de Janeiro
Luze Xu: University of Michigan

Journal of Global Optimization, 2021, vol. 81, issue 4, No 9, 1057-1093

Abstract: Abstract 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. Lett., 46:605–610, 2018) and Xu et al. (SIAM J. Optim., 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.

Keywords: Generalized inverse; Sparse optimization; Local search; Moore-Penrose pseudoinverse (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-01087-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:81:y:2021:i:4:d:10.1007_s10898-021-01087-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-021-01087-y

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().