Variable projection methods for approximate (greatest) common divisor computations

DOI10.1016/j.tcs.2017.03.028zbMath1375.65062arXiv1304.6962OpenAlexW2963113483MaRDI QIDQ2357371

Ivan Markovsky, Konstantin Usevich

Publication date: 13 June 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

least squares problemlinear complexitystructured low-rank approximationvariable projectionapproximate common divisor problemmosaic Hankel matricesweighted 2-norm

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Complexity and performance of numerical algorithms (65Y20) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Matrices, determinants in number theory (11C20) Toeplitz, Cauchy, and related matrices (15B05)

Related Items

Relaxed NewtonSLRA for approximate GCD ⋮ An ODE-based method for computing the approximate greatest common divisor of polynomials ⋮ SLRA Interpolation for Approximate GCD of Several Multivariate Polynomials ⋮ Structured low-rank approximation for nonlinear matrices ⋮ A Hybrid Penalty Method for a Class of Optimization Problems with Multiple Rank Constraints ⋮ Toward the best algorithm for approximate GCD of univariate polynomials ⋮ An ODE-Based Method for Computing the Distance of Coprime Polynomials to Common Divisibility

Uses Software

• ApaTools
• GSL
• GPGCD
• SLRA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A quadratically convergent algorithm for structured low-rank approximation
• GPGCD: an iterative method for calculating approximate GCD of univariate polynomials
• Computing the nearest singular univariate polynomials with given root multiplicities
• An improved non-linear method for the computation of a structured low rank approximation of the Sylvester resultant matrix
• Optimization on a Grassmann manifold with application to system identification
• A subdivision method for computing nearest gcd with certification
• Hybrid method for computing the nearest singular polynomials
• Algebraic methods for Toeplitz-like matrices and operators
• Common factor estimation and two applications in signal processing
• The ERES method for computing the approximate GCD of several polynomials
• On approximate GCDs of univariate polynomials
• An algorithm for computing certified approximate GCD of \(n\) univariate polynomials
• Common factor detection and estimation
• Computation of approximate polynomial GCDs and an extension
• Variable projection for affinely structured low-rank approximation in weighted \(2\)-norms
• Software for weighted structured low-rank approximation
• Approximate gcds of polynomials and sparse SOS relaxations
• Structured low-rank approximation and its applications
• Approximate greatest common divisor of many polynomials, generalised resultants, and strength of approximation
• Structured total least norm and approximate GCDs of inexact polynomials
• Structured Low-Rank Approximation with Missing Data
• Factorization Approach to Structured Low-Rank Approximation with Applications
• Blind image deconvolution via fast approximate GCD
• Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials
• The numerical greatest common divisor of univariate polynomials
• Frequency domain system identification with missing data
• Asymptotic Spectra of Hermitian Block Toeplitz Matrices and Preconditioning Results
• Exact Solutions in Structured Low-Rank Approximation
• Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars
• Matrix pencil methodologies for computing the greatest common divisor of polynomials: hybrid algorithms and their performance
• The Differentiation of Pseudo-Inverses and Nonlinear Least Squares Problems Whose Variables Separate