Concentration of the Frobenius norm of generalized matrix inverses

DOI10.1137/17M1145409zbMATH Open1407.15005arXiv1810.07921OpenAlexW2897477974WikidataQ128560612 ScholiaQ128560612MaRDI QIDQ4615303FDOQ4615303

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)

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.

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

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

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)

Cites Work

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

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)