A quadratically convergent algorithm for structured low-rank approximation
From MaRDI portal
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 , the goal is to compute a matrix of given rank in a linear or affine subspace of matrices (usually encoding a specific structure) such that the Frobenius distance 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 and the linear/affine subspace . 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 matrices in . 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.
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
Cites work
- scientific article; zbMATH DE number 3891516 (Why is no real title available?)
- scientific article; zbMATH DE number 5168246 (Why is no real title available?)
- scientific article; zbMATH DE number 47206 (Why is no real title available?)
- scientific article; zbMATH DE number 3461174 (Why is no real title available?)
- scientific article; zbMATH DE number 1254271 (Why is no real title available?)
- <tex>$QR$</tex>Factoring to Compute the GCD of Univariate Approximate Polynomials
- A modified Newton-Raphson method for the solution of systems of equations
- A simpler approach to matrix completion
- Alternating Projections on Manifolds
- An iterative method for calculating approximate GCD of univariate polynomials
- Approximate GCD a la dedieu
- Approximate factorization of multivariate polynomials using singular value decomposition
- Approximate factorization of multivariate polynomials via differential equations
- Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials
- Best approximation in inner product spaces
- Cadzow denoising upgraded: a new projection method for the recovery of Dirac pulses from noisy linear measurements
- Certified approximate univariate GCDs
- Computation of approximate polynomial GCDs and an extension
- Computing nearest gcd with certification
- Determinantal rings
- Exact matrix completion via convex optimization
- Exact solutions in structured low-rank approximation
- Fixed points, zeros and Newton's method
- Linear Sections of Determinantal Varieties
- Low rank approximation of a Hankel matrix by structured total least norm
- Low-rank matrix completion by Riemannian optimization
- Low-rank matrix completion using alternating minimization
- Newton's method for analytic systems of equations with constant rank derivatives
- On approximate GCDs of univariate polynomials
- Quasi-gcd computations
- Reducibility of polynomials \(f(x,y)\) modulo \(p\)
- Signal enhancement-a composite property mapping algorithm
- Structured Total Least Norm for Nonlinear Problems
- Structured low rank approximation
- Structured low rank approximations of the sylvester resultant matrix for approximate GCDS of Bernstein basis polynomials
- Structured low-rank approximation and its applications
- Structured matrix-based methods for polynomial \(\varepsilon\)-gcd: analysis and comparisons
- The Euclidean distance degree of an algebraic variety
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- The approximate GCD of inexact polynomials
- Two Newton methods on the manifold of fixed-rank matrices endowed with Riemannian quotient geometries
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
- ALORA: affine low-rank approximations
- An efficient Gauss-Newton algorithm for symmetric low-rank product matrix 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
- On the convergence of Stewart's QLP algorithm for approximating the SVD
- Exact solutions in structured low-rank approximation
- Variable projection methods for approximate (greatest) common divisor computations
- An ODE-based method for computing the approximate greatest common divisor of polynomials
- Real polynomial root-finding by means of matrix and polynomial iterations
- Approximate GCD of several multivariate sparse polynomials based on SLRA interpolation
- 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
- Implicit QR for rank-structured matrix pencils
- Exact solutions in low-rank approximation with zeros
- Implementation of fast low rank approximation of a Sylvester matrix
- Rank structured approximation method for quasi-periodic elliptic problems
- Computing approximate greatest common right divisors of differential polynomials
- Low-Rank Approximations with Sparse Factors II: Penalized Methods with Discrete Newton-Like Iterations
- Low-rank matrix iteration using polynomial-filtered subspace extraction
- Effective criteria for bigraded birational maps
- Variable projection for affinely structured low-rank approximation in weighted \(2\)-norms
- Implementation improvements and extensions of an ODE-based algorithm for structured low-rank approximation
- Structured low rank approximation of non-negative matrices
- Real root finding for low rank linear matrices
- Convex low rank approximation
- An Algorithm for Quadratic Eigenproblems with Low Rank Damping
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)
