Linearly Convergent Randomized Iterative Methods for Computing the Pseudoinverse

Robert Gower 1 Peter Richtárik 2
1 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
Abstract : We develop the first stochastic incremental method for calculating the Moore-Penrose pseu-doinverse of a real matrix. By leveraging three alternative characterizations of pseudoinverse matrices, we design three methods for calculating the pseudoinverse: two general purpose methods and one specialized to symmetric matrices. The two general purpose methods are proven to converge linearly to the pseudoinverse of any given matrix. For calculating the pseudoinverse of full rank matrices we present two additional specialized methods which enjoy a faster convergence rate than the general purpose methods. We also indicate how to develop randomized methods for calculating approximate range space projections, a much needed tool in inexact Newton type methods or quadratic solvers when linear constraints are present. Finally, we present numerical experiments of our general purpose methods for calculating pseudoinverses and show that our methods greatly outperform the Newton-Schulz method on large dimensional matrices.
Type de document :
Pré-publication, Document de travail
28 pages, 10 figures. 2017
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01430489
Contributeur : Robert Gower <>
Soumis le : lundi 9 janvier 2017 - 22:57:31
Dernière modification le : jeudi 11 janvier 2018 - 06:28:04
Document(s) archivé(s) le : lundi 10 avril 2017 - 16:49:09

Fichier

pseudo_inverse.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01430489, version 1

Collections

Citation

Robert Gower, Peter Richtárik. Linearly Convergent Randomized Iterative Methods for Computing the Pseudoinverse. 28 pages, 10 figures. 2017. 〈hal-01430489〉

Partager

Métriques

Consultations de la notice

169

Téléchargements de fichiers

90