Concentration of the Frobenius norm of generalized matrix inverses

DOI10.1137/17M1145409MaRDI QIDQ4615303zbMATH OpenOpenAlexWikidataFDO

Authors Ivan Dokmanić, Rémi Gribonval

Publication date 4 February 2019

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.07921

zbMATH Keywords

convex analysisrandom matricesFrobenius normconcentration bound\(\ell^p\) minimizationsparse pseudoinverse

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Theory of matrix inversion and generalized inverses (15A09)

Abstract: In many applications it is useful to replace the Moore-Penrose pseudoinverse (MPP) by a different generalized inverse with more favorable properties. We may want, for example, to have many zero entries, but without giving up too much of the stability of the MPP. One way to quantify stability is by how much the Frobenius norm of a generalized inverse exceeds that of the MPP. In this paper we derive finite-size concentration bounds for the Frobenius norm of $el{l}^p$-minimal general inverses of iid Gaussian matrices, with $1leqpleq2$. For $p=1$ we prove exponential concentration of the Frobenius norm of the sparse pseudoinverse; for $p=2$, we get a similar concentration bound for the MPP. Our proof is based on the convex Gaussian min-max theorem, but unlike previous applications which give asymptotic results, we derive finite-size bounds.

Recommendations

• The best generalized inverse
• The optimal perturbation bounds of the Moore-Penrose inverse under the Frobenius norm
• scientific article; zbMATH DE number 13128
• Perturbation bounds of generalized inverses
• Generalized inverses with respect to general norms

Cites work

• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 1405932 (Why is no real title available?)
• Adaptive greedy approximations
• Compressed sensing
• Convex graph invariants
• Corrupted Sensing: Novel Guarantees for Separating Structured Signals
• Designing Gabor windows using convex optimization
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Invertibility of random matrices: norm of the inverse
• Invertibility of symmetric random matrices
• Living on the edge: phase transitions in convex programs with random data
• Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
• On general minimax theorems
• On sparse reconstruction from Fourier and Gaussian measurements
• Optimally Sparse Frames
• Precise Error Analysis of Regularized <inline-formula> <tex-math notation="LaTeX">$M$ </tex-math> </inline-formula>-Estimators in High Dimensions
• Some inequalities for Gaussian processes and applications
• Sparse Approximate Solutions to Linear Systems
• Sparse dual frames and dual Gabor functions of minimal time and frequency supports
• Sparsity and spectral properties of dual frames
• Universality laws for randomized dimension reduction, with applications

Cited in

(3)

• Trading off \(1\)-norm and sparsity against rank for linear models using mathematical optimization: \(1\)-norm minimizing partially reflexive ah-symmetric generalized inverses
• Experimental analysis of local searches for sparse reflexive generalized inverses
• Theory of functional connections applied to quadratic and nonlinear programming under equality constraints

This page was built for publication: Concentration of the Frobenius norm of generalized matrix inverses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4615303)