Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix\n Recovery

2017/03/15 by Christian Kümmerle, Kümmerle, Christian, Juliane Sigl +1 · 2 citations
Computer Science · Engineering · Mathematics · #Algorithm #Applied mathematics #Blind Source Separation Techniques #Combinatorics #Computer science #Estimation theory #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Iterated function #Iteratively reweighted least squares #Least-squares function approximation #Low-rank approximation #Mathematical analysis #Mathematical optimization #Mathematics #Matrix (chemical analysis) #Matrix Theory and Algorithms #Matrix completion #Matrix norm #Medical Image Segmentation Techniques #Non-linear least squares #Norm (philosophy) #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Pure mathematics #Rank (graph theory) #Rate of convergence #Sparse and Compressive Sensing Techniques #Statistics

paper · pdf · doi:10.48550/arxiv.1703.05038

published in arXiv (Cornell University) 19(1), 1815-1863 (Cornell University)

openalex publication_date 2017/03/15 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28

Abstract

We propose a new iteratively reweighted least squares (IRLS) algorithm for\nthe recovery of a matrix X \∈ \ℂ^{d₁\× d₂} of rank r\n\≪\min(d₁,d₂) from incomplete linear observations, solving a sequence of\nlow complexity linear problems. The easily implementable algorithm, which we\ncall harmonic mean iteratively reweighted least squares (HM-IRLS), optimizes a\nnon-convex Schatten-p quasi-norm penalization to promote low-rankness and\ncarries three major strengths, in particular for the matrix completion setting.\nFirst, we observe a remarkable global convergence behavior of the algorithm's\niterates to the low-rank matrix for relevant, interesting cases, for which any\nother state-of-the-art optimization approach fails the recovery. Secondly,\nHM-IRLS exhibits an empirical recovery probability close to 1 even for a\nnumber of measurements very close to the theoretical lower bound r (d₁ +d₂\n-r), i.e., already for significantly fewer linear observations than any other\ntractable approach in the literature. Thirdly, HM-IRLS exhibits a locally\nsuperlinear rate of convergence (of order 2-p) if the linear observations\nfulfill a suitable null space property. While for the first two properties we\nhave so far only strong empirical evidence, we prove the third property as our\nmain theoretical result.\n

Citations

• Perturbation bounds in connection with singular value decomposition
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Iteratively reweighted least squares minimization for sparse recovery
• Matrix Completion has No Spurious Local Minimum

Cited by

• Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Training
• Approximation, Gelfand, and Kolmogorov numbers of Schatten class embeddings

Related

• Low-rank matrix recovery via iteratively reweighted least squares\n minimization
• Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares
• A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples
• Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method
• Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks