Real root finding for low rank linear matrices

DOI10.1007/S00200-019-00396-WMaRDI QIDQ2175227zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

low rank matricespolynomial system solvingreal algebraic geometrysymbolic computation

Mathematics Subject Classification ID

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

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.

Review text

In this paper, authors consider \(m\times s\) matrices (with \(m\geq s\)) in a real affine subspace of dimension \(n\), and they design computer algebra algorithms, based on advanced methods for polynomial system solving, to solve the following 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 the algorithm is polynomial in \(\binom{n+m(s-r)}{n}\) and thus, it improves on the state-of-the-art in computer algebra and effective real algebraic geometry. Computer experiments show the practical efficiency of the presented approach.

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

Cites work

• A Gröbner free alternative for polynomial system solving
• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• Algebraic degree in semidefinite and polynomial optimization
• Algorithms in real algebraic geometry
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions
• Deformation techniques for sparse systems
• Degeneracy loci and polynomial equation solving
• Determinantal Sets, Singularities and Application to Optimal Control in Medical Imagery
• Distortion varieties
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Exact algorithms for linear matrix inequalities
• Exact solutions in structured low-rank approximation
• FGb: A Library for Computing Gröbner Bases
• Geometry of algebraic curves. Volume II. With a contribution by Joseph Daniel Harris
• scientific article; zbMATH DE number 4132308 (Why is no real title available?)
• scientific article; zbMATH DE number 52497 (Why is no real title available?)
• scientific article; zbMATH DE number 3497890 (Why is no real title available?)
• scientific article; zbMATH DE number 3563286 (Why is no real title available?)
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 2151204 (Why is no real title available?)
• scientific article; zbMATH DE number 5223994 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• Moments, positive polynomials and their applications
• On the complexity of computing with zero-dimensional triangular sets
• On the complexity of the generalized MinRank problem
• Polar varieties and efficient real elimination
• Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
• Real root finding for determinants of linear matrices
• Real root finding for rank defects in linear Hankel matrices
• Solving systems of polynomial inequalities in subexponential time
• Solving zero-dimensional systems through the rational univariate representation

Cited in

(9)

• Real root finding for rank defects in linear Hankel matrices
• Real-Valued, Low Rank, Circulant Approximation
• Finding a low-rank basis in a matrix subspace
• Computing real solutions of polynomial systems via low-rank moment matrix completion
• Rational elimination algorithm and applications
• Effective lower bounds on the matrix rank and their applications
• Certifying solutions of degenerate semidefinite programs
• Unlabeled sensing using rank-one moment matrix completion
• Real root finding for determinants of linear matrices

Describes a project that uses

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)