Real root finding for low rank linear matrices

DOI10.1007/S00200-019-00396-WzbMATH Open1445.13026arXiv1506.05897OpenAlexW2212277022WikidataQ114692906 ScholiaQ114692906MaRDI QIDQ2175227FDOQ2175227

Authors: Didier Henrion, Simone Naldi, Mohab Safey El Din 

Publication date: 28 April 2020

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Abstract: We consider $mimess$ matrices (with $mgeqs$) in a real affine subspace of dimension $n$. The problem of finding elements of low rank in such spaces finds many applications in information and systems theory, where low rank is synonymous of structure and parsimony. We design computer algebra algorithms, based on advanced methods for polynomial system solving, to solve this problem efficiently and exactly: the input are the rational coefficients of the matrices spanning the affine subspace as well as the expected maximum rank, and the output is a rational parametrization encoding a finite set of points that intersects each connected component of the low rank real algebraic set. The complexity of our algorithm is studied thoroughly. It is polynomial in $$. It improves on the state-of-the-art in computer algebra and effective real algebraic geometry. Moreover, computer experiments show the practical efficiency of our approach.

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

Recommendations

• Real root finding for rank defects in linear Hankel matrices
• Real root finding for determinants of linear matrices
• A quadratically convergent algorithm for structured low-rank approximation
• Computing real solutions of polynomial systems via low-rank moment matrix completion
• On the low rank solutions for linear matrix inequalities

zbMATH Keywords

real algebraic geometrysymbolic computationpolynomial system solvinglow rank matrices

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Solving polynomial systems; resultants (13P15) Computational real algebraic geometry (14Q30)

Cites Work

• FGb: A Library for Computing Gröbner Bases
• Title not available (Why is that?)
• Title not available (Why is that?)
• Exact Solutions in Structured Low-Rank Approximation
• Moments, positive polynomials and their applications
• Title not available (Why is that?)
• Algorithms in real algebraic geometry
• Solving zero-dimensional systems through the rational univariate representation
• On the complexity of computing with zero-dimensional triangular sets
• Title not available (Why is that?)
• Geometry of algebraic curves. Volume II. With a contribution by Joseph Daniel Harris
• Title not available (Why is that?)
• A Gröbner free alternative for polynomial system solving
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Title not available (Why is that?)
• Solving systems of polynomial inequalities in subexponential time
• On the complexity of the generalized MinRank problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Deformation techniques for sparse systems
• Polar varieties and efficient real elimination
• Algebraic Degree in Semidefinite and Polynomial Optimization
• Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions
• Distortion varieties
• Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• Real root finding for determinants of linear matrices
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• Exact algorithms for linear matrix inequalities
• Degeneracy loci and polynomial equation solving
• Determinantal Sets, Singularities and Application to Optimal Control in Medical Imagery
• Real root finding for rank defects in linear Hankel matrices

Cited In (3)

• Real root finding for determinants of linear matrices
• Real root finding for rank defects in linear Hankel matrices
• Real-Valued, Low Rank, Circulant Approximation

Uses Software

• FGb
• Kronecker
• RAGlib
• ISOLATE
• SPECTRA

This page was built for publication: Real root finding for low rank linear matrices

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