Generate Sparse Reflexive Generalized Inverses
Given an m-by-n matrix M and r <= rank(M), [H,A]=ahsymginv(M,r) returns a rank-r approximation A of M, and an n-by-m matrix H satisfying (i) AHA=A, (ii) HAH=H, (iii) (AH)'=AH, (iv) having only r nonzero rows, and with low (vector) 1-norm. Such an H is a particular sparse, block-structured, minimum-rank generalized inverse of A, for which x=Hb also solves the least-squares problem min ||Ax-b||_2. If r=rank(M), then A=M.
[H,A,K]=ahsymginv(M,r), with three outputs arguments, also returns K, a list of r elements from 1:n, so that the dense r-by-m submatrix H_hat of H is given by pinv(A(:,K)). K is computed by a local-search algorithm, which aims to construct a lower (vector) 1-norm matrix H_hat.
ahsymginv(M,r) uses [R,C]=nsub(A,r) to initialize its local-search algorithm.
[H,A,K]=ahsymginv(M,r,R,C) functions as described above, but uses (R,C) to initialize its local-search algorithm, where R should be a list of r elements from 1:m, C should be a list of r elements from 1:n, and A(R,C) should be nonsingular.
See: M. Fampa, J. Lee, G. Ponte, L. Xu. Experimental analysis of local search for sparse reflexive generalized inverses. Journal of Global Optimization, 81:1057-1093, 2021.
Example:
r = 3; M = [-1 -1 1 1 -5; -1 -1 1 0 -5; 0 0 0 1 0; 2 1 1 1 1];
[H,A,K] = ahsymginv(M,r);
Result: H = [[-0.1481 0.2593 -0.4074 0.5556]; [ 0 0 0 0]; [ 0 0 0 0]; [ 0.3333 -0.3333 0.6667 0.0000]; [-0.0370 -0.1852 0.1481 -0.1111]]
rank(H) = 3; A=M; Note that, selecting for example b=[1;1;1;1], we have norm(A * H * b -b,2)=norm(A * pinv(A) * b-b,2)=0.5774
Cite As
Fampa, Marcia, et al. “Experimental Analysis of Local Searches for Sparse Reflexive Generalized Inverses.” Journal of Global Optimization, vol. 81, no. 4, Springer Science and Business Media LLC, Sept. 2021, pp. 1057–93, doi:10.1007/s10898-021-01087-y.
MATLAB Release Compatibility
Platform Compatibility
Windows macOS LinuxTags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.
Version | Published | Release Notes | |
---|---|---|---|
22.03.3 | See release notes for this release on GitHub: https://github.com/GabrielPonte/ahsymginv/releases/tag/22.03.3 |