Sparse symmetric generalized inverses for sparse symmetric matrices

Ananias Machado; Jon Lee; Marcia Fampa

Sparse symmetric generalized inverses for sparse symmetric matrices

T0 review · 0 major / 2 minor · reviewed 2026-06-29 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A new characterization of symmetric generalized inverses reduces 1-norm minimization to an affine problem solvable by Douglas-Rachford splitting with closed-form projection.

desk verdict The paper's main contribution is a clean affine characterization of symmetric generalized inverses that enables a closed-form DRS projection and better scalability than exact LP solvers. read the letter →

arxiv 2605.26318 v1 pith:XBJX6BKL submitted 2026-05-25 math.OC

Ananias Machado , Marcia Fampa , Jon Lee This is my paper · ORCID

classification math.OC

keywords generalizedinversessparsematricessymmetricDouglas-Rachfordsplitting1-normminimizationMoore-Penrosepseudoinverseleast-squaressolutions

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper develops a method to compute generalized inverses that stay sparse when the original symmetric matrix is sparse, in contrast to the dense Moore-Penrose pseudoinverse. The approach minimizes the vector 1-norm over the set of symmetric generalized inverses. A fresh characterization of these inverses produces a compact affine reformulation that supports an efficient Douglas-Rachford splitting algorithm equipped with a closed-form projection. Computational tests show the resulting inverses are substantially sparser and have smaller 1-norms than those from competing methods, while the algorithm handles problem sizes beyond the reach of commercial linear optimizers. The technique is illustrated on least-squares problems that involve many right-hand-side vectors and sparse rank-deficient design matrices.

What carries the argument

The new characterization of symmetric generalized inverses of symmetric matrices, which yields a compact affine reformulation admitting closed-form projection in the Douglas-Rachford splitting algorithm.

What would settle it

Running the Douglas-Rachford algorithm and an exact linear-optimization solver on the same collection of sparse symmetric test matrices and comparing the sparsity level and 1-norm of the resulting generalized inverses against each other and against the Moore-Penrose pseudoinverse.

Watch

Extended reading notes

Core claim

Symmetric generalized inverses of symmetric matrices admit a new characterization that yields a compact affine reformulation of the 1-norm minimization problem; this reformulation admits a closed-form projection, which the Douglas-Rachford splitting algorithm uses to produce generalized inverses that are substantially sparser than the Moore-Penrose pseudoinverse, maintain significantly smaller 1-norms than competing approaches, and scale to instances far beyond commercial solvers.

Load-bearing premise

The new characterization of symmetric generalized inverses of symmetric matrices yields a compact affine reformulation of the problem that admits a closed-form projection in the Douglas-Rachford algorithm.

Editorial extensions

If this is right

The produced generalized inverses are substantially sparser than the Moore-Penrose pseudoinverse.
They maintain significantly smaller 1-norms than those from competing local-search heuristics and exact formulations.
The Douglas-Rachford splitting algorithm solves instances far beyond the reach of commercial solvers.
The method supports computation of least-squares solutions for problems with many right-hand-side vectors and sparse rank-deficient design matrices.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The closed-form projection step may transfer to other splitting methods applied to matrix optimization problems with symmetry constraints.
If 1-norm minimization reliably promotes sparsity under the new characterization, analogous reformulations could be attempted for structured generalized inverses in other matrix classes.
The observed scalability suggests the approach could be embedded inside iterative solvers that repeatedly require generalized inverses of changing sparse symmetric matrices.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The central new piece is the characterization of symmetric generalized inverses for symmetric A that produces an affine constraint set, letting them minimize the vector 1-norm with Douglas-Rachford splitting and an explicit projection step. This extends their prior rectangular-matrix results and avoids the density of the Moore-Penrose pseudoinverse.

The approach is straightforward and the logic holds: the defining condition AGA = A is linear in the entries of G under the symmetry requirement, so the feasible set is indeed affine and the projection reduces to a linear solve whose size tracks the number of independent equations. The experiments, as summarized, show the method finds sparser solutions than the pseudoinverse, smaller 1-norms than competing heuristics, and solves instances that commercial solvers cannot handle. That scalability edge is the practical payoff for least-squares problems with many right-hand sides.

The main soft spot is the lack of detail on the test matrices and exact sparsity metrics in the abstract; without those, it is hard to judge how broadly the gains apply or whether they depend on particular sparsity patterns or rank profiles. The least-squares application is mentioned but not quantified, so its added value remains unclear. No load-bearing inconsistencies appear in the argument structure.

This work is aimed at people who compute generalized inverses inside larger optimization or statistical pipelines and care about storage and multiply cost. It is a targeted but solid algorithmic paper with testable claims. I would send it to peer review; the formulation is clean enough that referees can check the characterization and run the experiments themselves.

Referee Report

0 major / 2 minor

Summary. The paper claims that the set of symmetric generalized inverses G of a symmetric matrix A (i.e., AGA=A with G symmetric) admits a new linear characterization that makes the feasible set an affine subspace. Minimizing the vector 1-norm over this set yields sparse symmetric GIs; the resulting convex program is solved by a Douglas-Rachford splitting algorithm whose projection step is closed-form. Experiments on sparse symmetric test matrices show that the obtained GIs are substantially sparser than the Moore-Penrose pseudoinverse, have smaller 1-norms than those from local-search heuristics or exact LP formulations, and that the DRS method scales to instances beyond the reach of commercial solvers. An application to multi-RHS least-squares problems with sparse rank-deficient design matrices is also presented.

Significance. If the characterization and closed-form projection hold, the work supplies a practical, scalable route to sparse symmetric generalized inverses that avoids the density of the Moore-Penrose inverse while preserving the defining algebraic property. The fact that the projection reduces to the solution of a single linear system whose size is governed only by the number of independent constraints in AGA=A is a concrete algorithmic advantage. The reported scalability gains over exact linear-optimization solvers constitute a falsifiable, practically relevant improvement for large-scale sparse problems in numerical linear algebra.

minor comments (2)

The abstract asserts that the DRS method 'successfully solving instances far beyond the reach of commercial solvers,' yet the manuscript does not state the precise dimensions, sparsity patterns, or termination criteria used for the largest solved instances; adding a short table or paragraph with these parameters would strengthen the scalability claim.
Notation for the affine constraint set and the projection operator is introduced without an explicit equation number in the main text; numbering the defining linear system for the projection (currently described only in prose) would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work on sparse symmetric generalized inverses and for recommending minor revision. No specific major comments appear in the report.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity detected

full rationale

The derivation begins with the standard definition of a symmetric generalized inverse G satisfying AGA = A with G symmetric, then supplies an explicit new linear characterization that directly produces an affine feasible set without any auxiliary fitted quantities or self-referential definitions. The subsequent Douglas-Rachford splitting step uses a standard closed-form projection onto that affine space whose correctness follows from elementary linear algebra and does not rely on any result whose validity is established only inside the paper. Computational claims about sparsity and 1-norm improvement are empirical comparisons against external baselines (Moore-Penrose, commercial solvers, heuristics) and are not obtained by renaming or re-using quantities already present in the model. No self-citation chain, ansatz smuggling, or uniqueness theorem imported from the authors' prior work appears as a load-bearing premise. The entire chain therefore remains self-contained against external verification.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

Based solely on the abstract, the work relies on standard definitions and properties of generalized inverses and convex optimization without introducing new free parameters or postulated entities.

assumptions (1)

standard math Standard algebraic properties of symmetric generalized inverses and the Moore-Penrose pseudoinverse
The reformulation and comparison rest on these established definitions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Sparse symmetric generalized inverses for sparse symmetric matrices." pith.science (2026). https://pith.science/paper/XBJX6BKL

@misc{pith2026260526318,
  author       = {Pith},
  title        = {Pith review of: Sparse symmetric generalized inverses for sparse symmetric matrices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XBJX6BKL}},
  note         = {Machine review of arXiv:2605.26318}
}

read the original abstract

Generalized inverses play a fundamental role in numerical linear algebra, particularly when matrices are rectangular, singular, or rank deficient. Even when the input matrix is sparse, generalized inverses such as the M-P pseudoinverse are typically dense, leading to high storage requirements, expensive matrix-vector multiplications, and reduced efficiency. We investigate computing sparse symmetric generalized inverses for sparse symmetric matrices, extending previous work on sparse generalized inverses for rectangular rank-deficient matrices. We consider minimizing the vector 1-norm over the set of symmetric generalized inverses, using vector 1-norm minimization as a surrogate for sparsity promotion. We give a new characterization of symmetric generalized inverses of symmetric matrices, which yields a compact affine reformulation of the problem. From this, we develop a Douglas-Rachford splitting (DRS) algorithm equipped with a closed-form projection onto the feasible affine space. Computational experiments compare the proposed DRS approach with exact linear-optimization formulations solved by a commercial optimizer, as well as with local-search heuristics. The results demonstrate that the proposed formulation and algorithm produce generalized inverses that are substantially sparser than the Moore-Penrose pseudoinverse while maintaining significantly smaller 1-norms than competing approaches. Moreover, the DRS algorithm exhibits superior scalability relative to exact linear-optimization formulations, successfully solving instances far beyond the reach of commercial solvers. As an application, we investigate the computation of least-squares solutions for problems involving many right-hand-side vectors and sparse rank-deficient design matrices.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 15 canonical work pages

[1]

Generalized inverse of a matrix and its applications,

C. R. Rao and S. K. Mitra, “Generalized inverse of a matrix and its applications,” inProceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability. Volume I: Theory of Statistics (L. M. Le Cam, J. Neyman, and E. Scott, eds.), pp. 601–620, University of California Press, 1972.https: //doi.org/10.1525/9780520325883-032

work page doi:10.1525/9780520325883-032 1972
[2]

Approximate 1-norm minimization and minimum-rank structured sparsity for various generalized inverses via local search,

L. Xu, M. Fampa, J. Lee, and G. Ponte, “Approximate 1-norm minimization and minimum-rank structured sparsity for various generalized inverses via local search,”SIAM Journal on Optimization, vol. 31, no. 3, pp. 1722–1747, 2021.https://doi.org/10.1137/19M1281514

work page doi:10.1137/19m1281514 2021
[3]

G. H. Golub and C. F. Van Loan,Matrix Computations. Johns Hopkins University Press, 4th ed., 2013. https://epubs.siam.org/doi/abs/10.1137/1.9781421407944

work page doi:10.1137/1.9781421407944 2013
[4]

Mathematical Proceedings of the Cambridge Philosophical Society , author=

R. Penrose, “A generalized inverse for matrices,”Proceedings of the Cambridge Philosophical Society, vol. 51, pp. 406–413, 1955.https://doi.org/10.1017/S0305004100030401

work page doi:10.1017/s0305004100030401 1955
[5]

Ben-Israel and T

A. Ben-Israel and T. N. Greville,Generalized Inverses: Theory and Applications. Springer, 2nd ed., 2003. https://doi.org/10.1007/b97366

work page doi:10.1007/b97366 2003
[6]

On computing sparse generalized inverses,

G. Ponte, M. Fampa, J. Lee, and L. Xu, “On computing sparse generalized inverses,”Operations Research Letters, vol. 52, p. 107058, 2024.https://doi.org/10.1016/j.orl.2023.107058

work page doi:10.1016/j.orl.2023.107058 2024
[7]

Beyond Moore-Penrose: sparse pseudoinverse,

I. Dokmanić, M. Kolundžija, and M. Vetterli, “Beyond Moore-Penrose: sparse pseudoinverse,” inICASSP 2013 (38th International Conference on Acoustics, Speech, and Signal Processing),pp. 6526–6530, IEEE, 2013.https://doi.org/10.1109/ICASSP.2013.6638923

work page doi:10.1109/icassp.2013.6638923 2013
[8]

Beyond Moore-Penrose Part I: generalized inverses that minimize matrix norms,

I. Dokmanić and R. Gribonval, “Beyond Moore-Penrose Part I: generalized inverses that minimize matrix norms,” 2017.https://inria.hal.science/hal-01547183v1/document

2017

Show all 21 references

[9]

Beyond Moore-Penrose Part II: the sparse pseudoinverse,

I. Dokmanić and R. Gribonval, “Beyond Moore-Penrose Part II: the sparse pseudoinverse,” 2017.https: //hal.inria.fr/hal-01547283/file/pseudo-part2.pdf

2017
[10]

Sparse pseudoinverses via LP and SDP relaxations of Moore- Penrose,

V. K. Fuentes, M. Fampa, and J. Lee, “Sparse pseudoinverses via LP and SDP relaxations of Moore- Penrose,” inCLAIO 2016 (18th Latin-Iberian-American Conference on Operations Research), pp. 343–350, 2016.https://marciafampa.com/pdf/CLAIO_2016_Proceedings_FuentesFampaLee.pdf

2016
[11]

On sparse reflexive generalized inverses,

M. Fampa and J. Lee, “On sparse reflexive generalized inverses,”Operations Research Letters, vol. 46, no. 6, pp. 605–610, 2018.https://doi.org/10.1016/j.orl.2018.09.005

2018 doi
[12]

1-norm minimization and minimum-rank structured sparsity for sym- metric and ah-symmetric generalized inverses: rank one and two,

L. Xu, M. Fampa, and J. Lee, “1-norm minimization and minimum-rank structured sparsity for sym- metric and ah-symmetric generalized inverses: rank one and two,” 2020. To appear in:Fields Insti- tute Communications volume on Data Science and Optimization,A. Deza, S. Gupta, S. P...

2020
[13]

Experimental analysis of local searches for sparse reflexive generalized inverses,

M. Fampa, J. Lee, G. Ponte, and L. Xu, “Experimental analysis of local searches for sparse reflexive generalized inverses,”Journal of Global Optimization, vol. 81, pp. 1057–1093, 2021.https://doi.org/10. 1007/s10898-021-01087-y

2021
[14]

Good and fast row-sparse ah-symmetric reflexive generalized inverses,

G. Ponte, M. Fampa, J. Lee, and L. Xu, “Good and fast row-sparse ah-symmetric reflexive generalized inverses,” 2024.https://arxiv.org/abs/2401.17540

2024
[15]

Oncomputingsparseuniversalsolversforkeyproblemsinstatistics,

A.S.Machado, M.Fampa, andJ.Lee, “Oncomputingsparseuniversalsolversforkeyproblemsinstatistics,” 2025.https://arxiv.org/abs/2509.04264

2025 arXiv
[16]

Optimization with first order algorithms,

C. Dossal, S. Hurault, and N. Papadakis, “Optimization with first order algorithms,” 2024.https:// arxiv.org/abs/2410.19506

2024
[17]

Anderson accelerated Douglas-Rachford splitting,

A. Fu, J. Zhang, and S. Boyd, “Anderson accelerated Douglas-Rachford splitting,”SIAM Journal on Sci- entific Computing, vol. 42, no. 6, p. A3560–A3583, 2020.http://dx.doi.org/10.1137/19M1290097

2020 doi
[18]

H. H. Bauschke and P. L. Combettes,Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics, Springer Science & Business Media, 2017.https://doi.org/10.1007/ 978-3-319-48311-5

2017
[19]

Proximal algorithms,

N. Parikh and S. Boyd, “Proximal algorithms,”Foundations and Trends in Optimization, vol. 1, no. 3, pp. 127–239, 2014.https://doi.org/10.1561/2400000003

2014 doi
[20]

C. A. Rohde,Contributions to the Theory, Computation and Application of Generalized Inverses. PhD thesis, University of North Carolina, Raleigh, N.C., May 1964.http://www.lib.ncsu.edu/resolver/ 1840.4/2316

1964
[21]

The University of Florida sparse matrix collection,

T. A. Davis and Y. Hu, “The University of Florida sparse matrix collection,”ACM Transactions on Math- ematical Software (TOMS), vol. 38, no. 1, pp. 1–25, 2011.https://doi.org/10.1145/2049662.2049663

2011 doi

Pith tools

Reviewed June 29, 2026 · model on record in the stance chip above.

[1] [1]

Generalized inverse of a matrix and its applications,

C. R. Rao and S. K. Mitra, “Generalized inverse of a matrix and its applications,” inProceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability. Volume I: Theory of Statistics (L. M. Le Cam, J. Neyman, and E. Scott, eds.), pp. 601–620, University of California Press, 1972.https: //doi.org/10.1525/9780520325883-032

work page doi:10.1525/9780520325883-032 1972

[2] [2]

Approximate 1-norm minimization and minimum-rank structured sparsity for various generalized inverses via local search,

L. Xu, M. Fampa, J. Lee, and G. Ponte, “Approximate 1-norm minimization and minimum-rank structured sparsity for various generalized inverses via local search,”SIAM Journal on Optimization, vol. 31, no. 3, pp. 1722–1747, 2021.https://doi.org/10.1137/19M1281514

work page doi:10.1137/19m1281514 2021

[3] [3]

G. H. Golub and C. F. Van Loan,Matrix Computations. Johns Hopkins University Press, 4th ed., 2013. https://epubs.siam.org/doi/abs/10.1137/1.9781421407944

work page doi:10.1137/1.9781421407944 2013

[4] [4]

Mathematical Proceedings of the Cambridge Philosophical Society , author=

R. Penrose, “A generalized inverse for matrices,”Proceedings of the Cambridge Philosophical Society, vol. 51, pp. 406–413, 1955.https://doi.org/10.1017/S0305004100030401

work page doi:10.1017/s0305004100030401 1955

[5] [5]

Ben-Israel and T

A. Ben-Israel and T. N. Greville,Generalized Inverses: Theory and Applications. Springer, 2nd ed., 2003. https://doi.org/10.1007/b97366

work page doi:10.1007/b97366 2003

[6] [6]

On computing sparse generalized inverses,

G. Ponte, M. Fampa, J. Lee, and L. Xu, “On computing sparse generalized inverses,”Operations Research Letters, vol. 52, p. 107058, 2024.https://doi.org/10.1016/j.orl.2023.107058

work page doi:10.1016/j.orl.2023.107058 2024

[7] [7]

Beyond Moore-Penrose: sparse pseudoinverse,

I. Dokmanić, M. Kolundžija, and M. Vetterli, “Beyond Moore-Penrose: sparse pseudoinverse,” inICASSP 2013 (38th International Conference on Acoustics, Speech, and Signal Processing),pp. 6526–6530, IEEE, 2013.https://doi.org/10.1109/ICASSP.2013.6638923

work page doi:10.1109/icassp.2013.6638923 2013

[8] [8]

Beyond Moore-Penrose Part I: generalized inverses that minimize matrix norms,

I. Dokmanić and R. Gribonval, “Beyond Moore-Penrose Part I: generalized inverses that minimize matrix norms,” 2017.https://inria.hal.science/hal-01547183v1/document

2017