Open Journal of Mathematical Optimization

Good and Fast Row-Sparse ah-Symmetric Reflexive Generalized Inverses
Gabriel Ponte1; Marcia Fampa2; Jon Lee1; Luze Xu3
1 University of Michigan, Ann Arbor, USA
2 Federal University of Rio de Janeiro, Brazil
3 University of California, Davis, USA
Open Journal of Mathematical Optimization, Volume 6 (2025), article no. 12, 24 p.

We present several algorithms aimed at constructing sparse and structured sparse (row-sparse) generalized inverses, with application to the efficient computation of least-squares solutions, for inconsistent systems of linear equations, in the setting of multiple right-hand sides and a rank-deficient constraint matrix. Leveraging our earlier formulations to minimize the 1- and 2,1-norms of generalized inverses that satisfy important properties of the Moore–Penrose pseudoinverse, we develop efficient and scalable ADMM algorithms to address these norm-minimization problems and to limit the number of nonzero rows in the solution. We establish a 2,1-norm approximation result for a local-search procedure that was originally designed for 1-norm minimization, and we compare the ADMM algorithms with the local-search procedure and with general-purpose optimization solvers.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/ojmo.48
Keywords: Moore–Penrose properties, generalized inverse, sparse optimization, norm minimization, least squares, local search, convex optimization, ADMM

Gabriel Ponte 1; Marcia Fampa 2; Jon Lee 1; Luze Xu 3

1 University of Michigan, Ann Arbor, USA
2 Federal University of Rio de Janeiro, Brazil
3 University of California, Davis, USA
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{OJMO_2025__6__A12_0,
     author = {Gabriel Ponte and Marcia Fampa and Jon Lee and Luze Xu},
     title = {Good and {Fast} {Row-Sparse} {ah-Symmetric} {Reflexive} {Generalized} {Inverses}},
     journal = {Open Journal of Mathematical Optimization},
     eid = {12},
     pages = {1--24},
     year = {2025},
     publisher = {Universit\'e de Montpellier},
     volume = {6},
     doi = {10.5802/ojmo.48},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.48/}
}
TY  - JOUR
AU  - Gabriel Ponte
AU  - Marcia Fampa
AU  - Jon Lee
AU  - Luze Xu
TI  - Good and Fast Row-Sparse ah-Symmetric Reflexive Generalized Inverses
JO  - Open Journal of Mathematical Optimization
PY  - 2025
SP  - 1
EP  - 24
VL  - 6
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.48/
DO  - 10.5802/ojmo.48
LA  - en
ID  - OJMO_2025__6__A12_0
ER  - 
%0 Journal Article
%A Gabriel Ponte
%A Marcia Fampa
%A Jon Lee
%A Luze Xu
%T Good and Fast Row-Sparse ah-Symmetric Reflexive Generalized Inverses
%J Open Journal of Mathematical Optimization
%D 2025
%P 1-24
%V 6
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.48/
%R 10.5802/ojmo.48
%G en
%F OJMO_2025__6__A12_0
Gabriel Ponte; Marcia Fampa; Jon Lee; Luze Xu. Good and Fast Row-Sparse ah-Symmetric Reflexive Generalized Inverses. Open Journal of Mathematical Optimization, Volume 6 (2025), article  no. 12, 24 p.. doi: 10.5802/ojmo.48

[1] Adi Ben-Israel; Thomas N. E. Greville Generalized Inverses: Theory and Applications, Springer, 1974 | DOI | Zbl | MR

[2] Stephen Boyd; Neal Parikh; Eric Chu; Borja Peleato; Jonathan Eckstein Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., Volume 3 (2011) no. 1, pp. 1-122 | DOI | Zbl

[3] Stephen L. Campbell; Carl D. Meyer Generalized Inverses of Linear Transformations, Society for Industrial and Applied Mathematics, 2009 | DOI | MR | Zbl

[4] Venkat Chandrasekaran; Sujay Sanghavi; Pablo A. Parrilo; Alan S. Willsky Rank-Sparsity Incoherence for Matrix Decomposition, SIAM J. Optim., Volume 21 (2011) no. 2, pp. 572-596 | DOI | Zbl | MR

[5] Ivan Dokmanić; Rémi Gribonval Beyond Moore–Penrose Part I: generalized inverses that minimize matrix norms, 2017 (https://inria.hal.science/hal-01547183v1/document)

[6] Ivan Dokmanić; Rémi Gribonval Beyond Moore–Penrose Part II: the sparse pseudoinverse, 2017 (https://hal.inria.fr/hal-01547283/file/pseudo-part2.pdf)

[7] Ivan Dokmanić; Mihailo Kolundžija; Martin Vetterli Beyond Moore–Penrose: sparse pseudoinverse, 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, IEEE, 2013, pp. 6526-6530 | DOI

[8] Marcia Fampa; Jon Lee On sparse reflexive generalized inverses, Oper. Res. Lett., Volume 46 (2018) no. 6, pp. 605-610 | DOI | Zbl | MR

[9] Marcia Fampa; Jon Lee; Gabriel Ponte Trading off 1-norm and sparsity against rank for linear models using mathematical optimization: 1-norm minimizing partially reflexive ah-symmetric generalized inverses, Open J. Math. Optim., Volume 2 (2021), 4, 14 pages | DOI | Numdam | Zbl | MR

[10] Marcia Fampa; Jon Lee; Gabriel Ponte; Luze Xu Experimental analysis of local searches for sparse reflexive generalized inverses, J. Glob. Optim., Volume 81 (2021), pp. 1057-1093 | DOI | Zbl | MR

[11] Victor K. Fuentes; Marcia Fampa; Jon Lee Sparse pseudoinverses via LP and SDP relaxations of Moore–Penrose, CLAIO 2016 (18th Latin-Iberian-American Conference on Operations Research) (2016), pp. 343-350 https://marciafampa.com/...

[12] Gene H. Golub; Charles F. Van Loan Matrix Computations (3rd Ed.), Johns Hopkins University Press, 1996 https://convexoptimization.com/... | Zbl | MR

[13] Jun Liu; Shuiwang Ji; Jieping Ye Multi-task feature learning via efficient l 2,1 -norm minimization, UAI’09: Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, AUAI Press (2009), pp. 339-348

[14] Zekun Liu; Siwei Yu Alternating Direction Method of Multipliers Based on ℓ 2,0 -Norm for Multiple Measurement Vector Problem, IEEE Trans. Signal Process., Volume 71 (2023), pp. 3490-3501 https://ieeexplore.ieee.org/document/10252024 | Zbl | MR

[15] Zhongyuan Lyu; Dong Xia Optimal estimation and computational limit of low-rank Gaussian mixtures, Ann. Stat., Volume 51 (2023) no. 2, pp. 646-667 | DOI | Zbl | MR

[16] Lukas Meier; Sara Van De Geer; Peter Bühlmann The group lasso for logistic regression, J. R. Stat. Soc., Ser. B, Stat. Methodol., Volume 70 (2008) no. 1, pp. 53-71 | DOI | Zbl | MR

[17] Karthik Mohan Learning structured matrices in high dimensions: Low rank estimation and structured graphical models, Ph. D. Thesis, University of Washington (2015) (http://hdl.handle.net/1773/33147)

[18] Guillaume R Obozinski; Martin J Wainwright; Michael Jordan High-dimensional support union recovery in multivariate regression, Advances in Neural Information Processing Systems 21 (NIPS 2008) (D. Koller; D. Schuurmans; Y. Bengio; L. Bottou, eds.), Curran Associates, Inc. (2008), pp. 1217-1224 https://proceedings.neurips.cc/...

[19] Roger Penrose A generalized inverse for matrices, Math. Proc. Camb. Philos. Soc., Volume 51 (1955), pp. 406-413 | DOI | Zbl | MR

[20] Gabriel Ponte; Marcia Fampa; Jon Lee; Luze Xu On computing sparse generalized inverses, Oper. Res. Lett., Volume 52 (2024), 107058, 6 pages | MR | DOI | Zbl

[21] Charles A. Rohde Contributions to the theory, computation and application of generalized inverses, Ph. D. Thesis, North Carolina State University, Raleigh (1964) (https://www4.stat.ncsu.edu/~boos/library/mimeo.archive/isms_1964_392.pdf)

[22] Yu Wang; Wotao Yin; Jinshan Zeng Global Convergence of ADMM in Nonconvex Nonsmooth Optimization, J. Sci. Comput., Volume 78 (2019) no. 1, pp. 29-63 | DOI | Zbl | MR

[23] Luze Xu; Marcia Fampa; Jon Lee 1-norm minimization and minimum-rank structured sparsity for symmetric and ah-symmetric generalized inverses: rank one and two 2020, to appear in S. Dang, A. Deza, S. Gupta, P. McNicholas, S. Pokutta, M. Sugiyama (eds.) Data Science and Optimization, volume 91 of Fields Institute Communications, Springer, ISBN 978-3-032-03843-2 | arXiv

[24] Luze Xu; Marcia Fampa; Jon Lee; Gabriel Ponte Approximate 1-norm minimization and minimum-rank structured sparsity for various generalized inverses via local search, SIAM J. Optim., Volume 31 (2021) no. 3, pp. 1722-1747 | DOI | Zbl | MR

[25] Ming Yuan; Yi Lin Model selection and estimation in regression with grouped variables, J. R. Stat. Soc., Ser. B, Stat. Methodol., Volume 68 (2006) no. 1, pp. 49-67 | DOI | Zbl | MR

[26] Hui Zou; Lingzhou Xue A Selective Overview of Sparse Principal Component Analysis, Proc. IEEE, Volume 106 (2018) no. 8, pp. 1311-1320 | DOI

Cited by Sources: