A quadratically convergent algorithm for structured low-rank approximation

DOI10.1007/S10208-015-9256-XzbMATH Open1347.65080arXiv1312.7279OpenAlexW2127771846MaRDI QIDQ285440FDOQ285440

Authors: Éric Schost, Pierre-Jean Spaenlehauer 

Publication date: 19 May 2016

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: Structured Low-Rank Approximation is a problem arising in a wide range of applications in Numerical Analysis and Engineering Sciences. Given an input matrix $M$, the goal is to compute a matrix $M^{\prime }$ of given rank $r$ in a linear or affine subspace $E$ of matrices (usually encoding a specific structure) such that the Frobenius distance $lVertM-M^{\prime }Vert$ is small. We propose a Newton-like iteration for solving this problem, whose main feature is that it converges locally quadratically to such a matrix under mild transversality assumptions between the manifold of matrices of rank $r$ and the linear/affine subspace $E$. We also show that the distance between the limit of the iteration and the optimal solution of the problem is quadratic in the distance between the input matrix and the manifold of rank $r$ matrices in $E$. To illustrate the applicability of this algorithm, we propose a Maple implementation and give experimental results for several applicative problems that can be modeled by Structured Low-Rank Approximation: univariate approximate GCDs (Sylvester matrices), low-rank Matrix completion (coordinate spaces) and denoising procedures (Hankel matrices). Experimental results give evidence that this all-purpose algorithm is competitive with state-of-the-art numerical methods dedicated to these problems.

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

Recommendations

• Factorization approach to structured low-rank approximation with applications
• Stochastic algorithms for solving structured low-rank matrix approximation problems
• Structured low rank approximation
• The alternating projection method for solving structured low rank approximation
• Exact solutions in structured low-rank approximation

zbMATH Keywords

matrix completionalgorithmHankel matricesquadratic convergenceapproximate greatest common divisorNewton iterationstructured low-rank approximation

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Matrix completion problems (15A83) Iterative numerical methods for linear systems (65F10)

Cites Work

• Exact matrix completion via convex optimization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Title not available (Why is that?)
• Exact solutions in structured low-rank approximation
• The Euclidean distance degree of an algebraic variety
• Title not available (Why is that?)
• Best approximation in inner product spaces
• Fixed points, zeros and Newton's method
• Low-rank matrix completion by Riemannian optimization
• Title not available (Why is that?)
• Linear Sections of Determinantal Varieties
• Quasi-gcd computations
• Determinantal rings
• On approximate GCDs of univariate polynomials
• Reducibility of polynomials \(f(x,y)\) modulo \(p\)
• Certified approximate univariate GCDs
• Newton's method for analytic systems of equations with constant rank derivatives
• Computation of approximate polynomial GCDs and an extension
• Structured low rank approximation
• Low rank approximation of a Hankel matrix by structured total least norm
• Two Newton methods on the manifold of fixed-rank matrices endowed with Riemannian quotient geometries
• A modified Newton-Raphson method for the solution of systems of equations
• Structured low-rank approximation and its applications
• Approximate factorization of multivariate polynomials using singular value decomposition
• Cadzow denoising upgraded: a new projection method for the recovery of Dirac pulses from noisy linear measurements
• An iterative method for calculating approximate GCD of univariate polynomials
• Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials
• Computing nearest gcd with certification
• Approximate GCD a la dedieu
• Title not available (Why is that?)
• Signal enhancement-a composite property mapping algorithm
• Title not available (Why is that?)
• Structured Total Least Norm for Nonlinear Problems
• Approximate factorization of multivariate polynomials via differential equations
• The approximate GCD of inexact polynomials
• Structured matrix-based methods for polynomial \(\varepsilon\)-gcd: analysis and comparisons
• <tex>$QR$</tex>Factoring to Compute the GCD of Univariate Approximate Polynomials
• Alternating Projections on Manifolds
• A simpler approach to matrix completion
• Low-rank matrix completion using alternating minimization
• Structured low rank approximations of the sylvester resultant matrix for approximate GCDS of Bernstein basis polynomials

Cited In (35)

• Relaxed NewtonSLRA for approximate GCD
• Computing lower rank approximations of matrix polynomials
• Structured low-rank approximation: optimization on matrix manifold approach
• Approximate square-free part and decomposition
• Computation of the nearest non-prime polynomial matrix: structured low-rank approximation approach
• An O(n) algorithm for least squares quasi-convex approximation
• An efficient Gauss-Newton algorithm for symmetric low-rank product matrix approximations
• ALORA: affine low-rank approximations
• On critical points of quadratic low-rank matrix optimization problems
• The alternating projection method for solving structured low rank approximation
• A class of multilevel structured low-rank approximation arising in material processing
• A convex relaxation to compute the nearest structured rank deficient matrix
• Exact solutions in structured low-rank approximation
• On the convergence of Stewart's QLP algorithm for approximating the SVD
• Variable projection methods for approximate (greatest) common divisor computations
• An ODE-based method for computing the approximate greatest common divisor of polynomials
• Approximate GCD of several multivariate sparse polynomials based on SLRA interpolation
• Real polynomial root-finding by means of matrix and polynomial iterations
• Grassmann algorithms for low rank approximation of matrices with missing values
• Harmonic mean iteratively reweighted least squares for low-rank matrix recovery
• SLRA Interpolation for Approximate GCD of Several Multivariate Polynomials
• Exact solutions in low-rank approximation with zeros
• Implicit QR for rank-structured matrix pencils
• Implementation of fast low rank approximation of a Sylvester matrix
• Low-Rank Approximations with Sparse Factors II: Penalized Methods with Discrete Newton-Like Iterations
• Rank structured approximation method for quasi-periodic elliptic problems
• Computing approximate greatest common right divisors of differential polynomials
• Low-rank matrix iteration using polynomial-filtered subspace extraction
• Effective criteria for bigraded birational maps
• Implementation improvements and extensions of an ODE-based algorithm for structured low-rank approximation
• Variable projection for affinely structured low-rank approximation in weighted \(2\)-norms
• Structured low rank approximation of non-negative matrices
• Real root finding for low rank linear matrices
• An Algorithm for Quadratic Eigenproblems with Low Rank Damping
• Convex low rank approximation

Uses Software

• Maple
• MultRoot

This page was built for publication: A quadratically convergent algorithm for structured low-rank approximation

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