# Beyond Moore-Penrose Part II: The Sparse Pseudoinverse

2 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
Inria Rennes – Bretagne Atlantique , IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE
Abstract : This is the second part of a two-paper series on generalized inverses that minimize matrix norms. In Part II we focus on generalized inverses that are minimizers of entrywise p norms whose main representative is the sparse pseudoinverse for $p = 1$. We are motivated by the idea to replace the Moore-Penrose pseudoinverse by a sparser generalized inverse which is in some sense well-behaved. Sparsity implies that it is faster to apply the resulting matrix; well-behavedness would imply that we do not lose much in stability with respect to the least-squares performance of the MPP. We first address questions of uniqueness and non-zero count of (putative) sparse pseu-doinverses. We show that a sparse pseudoinverse is generically unique, and that it indeed reaches optimal sparsity for almost all matrices. We then turn to proving our main stability result: finite-size concentration bounds for the Frobenius norm of p-minimal inverses for $1 ≤ p ≤ 2$. Our proof is based on tools from convex analysis and random matrix theory, in particular the recently developed convex Gaussian min-max theorem. Along the way we prove several results about sparse representations and convex programming that were known folklore, but of which we could find no proof.
Document type :
Preprints, Working Papers, ...
Domain :

Cited literature [24 references]

https://hal.inria.fr/hal-01547283
Contributor : Rémi Gribonval Connect in order to contact the contributor
Submitted on : Thursday, July 13, 2017 - 11:28:04 PM
Last modification on : Saturday, August 6, 2022 - 3:32:54 AM
Long-term archiving on: : Friday, January 26, 2018 - 8:09:39 PM

### Files

pseudo-part2.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-01547283, version 2
• ARXIV : 1706.08701

### Citation

Ivan Dokmanić, Rémi Gribonval. Beyond Moore-Penrose Part II: The Sparse Pseudoinverse. 2017. ⟨hal-01547283v2⟩

Record views