Optimizing sparsity over lattices and semigroups

DOI10.1007/978-3-030-45771-6_4MaRDI QIDQ5041733zbMATH OpenOpenAlexFDO

Authors Gennadiy Averkov, Jesús A. De Loera, Timm Oertel, Iskander Aliev

Publication date 14 October 2022

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

boundsnon-zero entries of a solutionpolynomial time algorithms

Mathematics Subject Classification ID

Integer programming (90C10)

Abstract: Motivated by problems in optimization we study the sparsity of the solutions to systems of linear Diophantine equations and linear integer programs, i.e., the number of non-zero entries of a solution, which is often referred to as the $el{l}_0$-norm. Our main results are improved bounds on the $el{l}_0$-norm of sparse solutions to systems $Ax=b$, where $Ainmathbb{Z}^{mimesn}$, $binmathbb{Z}^m$ and $x$ is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In the lattice case and certain scenarios of the semigroup case, we give polynomial time algorithms for computing solutions with $el{l}_0$-norm satisfying the obtained bounds.

Recommendations

• Sparse representation of vectors in lattices and semigroups
• Sparse Solutions of Linear Diophantine Equations
• Sparse solutions of a class of constrained optimization problems
• Complementarity formulations of \(\ell_0\)-norm optimization
• Sparsity of integer solutions in the average case

Cites work

• A survey of compressed sensing
• An algebraic perspective on integer sparse recovery
• An introduction to the theory of numbers. Edited and revised by D. R. Heath-Brown and J. H. Silverman. With a foreword by Andrew Wiles
• Carathéodory bounds for integer cones
• Complexity of the Frobenius problem
• Decoding by Linear Programming
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• Lattice translates of a polytope and the Frobenius problem
• Matching structure and the matching lattice
• Non-unique factorizations. Algebraic, combinatorial and analytic theory
• On the recovery of an integer vector from linear measurements
• On the size of lattice simplices with a single interior lattice point
• PROMP: a sparse recovery approach to lattice-valued signals
• Short rational generating functions for lattice point problems
• Sparse Approximate Solutions to Linear Systems
• Sparse Solutions of Linear Diophantine Equations
• Sparsity of integer solutions in the average case
• Spatial Compressive Sensing for MIMO Radar
• Stable signal recovery from incomplete and inaccurate measurements
• The support of integer optimal solutions

Cited in

(6)

• Sparse representation of vectors in lattices and semigroups
• On sparse geometry of numbers
• Generalized flatness constants, spanning lattice polytopes, and the Gromov width
• The distributions of functions related to parametric integer optimization
• Distance-sparsity transference for vertices of corner polyhedra
• scientific article; zbMATH DE number 6607548 (Why is no real title available?)

This page was built for publication: Optimizing sparsity over lattices and semigroups

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