# Sparse Approximate Solutions to Linear Systems

@article{Natarajan1995SparseAS, title={Sparse Approximate Solutions to Linear Systems}, author={Balas K. Natarajan}, journal={SIAM J. Comput.}, year={1995}, volume={24}, pages={227-234} }

The following problem is considered: given a matrix $A$ in ${\bf R}^{m \times n}$, ($m$ rows and $n$ columns), a vector $b$ in ${\bf R}^m$, and ${\bf \epsilon} > 0$, compute a vector $x$ satisfying $\| Ax - b \|_2 \leq {\bf \epsilon}$ if such exists, such that $x$ has the fewest number of non-zero entries over all such vectors. It is shown that the problem is NP-hard, but that the well-known greedy heuristic is good in that it computes a solution with at most $\left\lceil 18 \mbox{ Opt} ({\bf… Expand

#### Topics from this paper

#### 2,454 Citations

A Perturbation Inequality for the Schatten-$p$ Quasi-Norm and Its Applications to Low-Rank Matrix Recovery

- Mathematics, Computer Science
- ArXiv
- 2012

A perturbation inequality for the so--called Schatten $p$--quasi--norm is obtained, which allows the validity of a number of previously conjectured conditions for the recovery of low--rank matrices via the popular Schatten p-norm heuristic to be confirmed. Expand

Sparse representation of vectors in lattices and semigroups

- Mathematics
- 2021

We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries,… Expand

Recovery of sparsest signals via $\ell^q$-minimization

- Mathematics
- 2010

In this paper, it is proved that every $s$-sparse vector ${\bf x}\in {\mathbb R}^n$ can be exactly recovered from the measurement vector ${\bf z}={\bf A} {\bf x}\in {\mathbb R}^m$ via some… Expand

Sparse Convex Optimization via Adaptively Regularized Hard Thresholding

- Computer Science, Mathematics
- ICML
- 2020

A new Adaptively Regularized Hard Thresholding (ARHT) algorithm that makes significant progress on this problem by bringing the bound down to $\gamma=O(\kappa)$, which has been shown to be tight for a general class of algorithms including LASSO, OMP, and IHT. Expand

Recovery of Sparse Representations by Polytope Faces Pursuit

- Mathematics, Computer Science
- ICA
- 2006

The proposed algorithm, which is based on the geometry of the polar polytope, is called Polytope Faces Pursuit and produces good results on examples that are known to be hard for MP, and it is faster than the interior point method for BP on the experiments presented. Expand

Recovery of sparsest signals via ℓq-minimization

- Mathematics, Computer Science
- ArXiv
- 2010

It is proved that every s-sparse vector in R can be exactly recovered from the measurement vector z via some $\ell^q$-minimization with 0< q\le 1$. Expand

Sparse Regression via Range Counting

- Mathematics, Computer Science
- SWAT
- 2020

This work describes a $O(n^{k-1} \log^{d-k+2} n)-time randomized $(1+\varepsilon)$-approximation algorithm for the sparse regression problem, and provides a simple $O_\delta(n-1+ \delta})-time deterministic exact algorithm, for any \(\delta > 0\). Expand

Complexity of unconstrained $$L_2-L_p$$ minimization

- Mathematics, Computer Science
- Math. Program.
- 2014

Theoretical results show that the minimizers of the L_q-L_p minimization problem have various attractive features due to the concavity and non-Lipschitzian property of the regularization function. Expand

Sparse solutions of linear complementarity problems

- Mathematics, Computer Science
- Math. Program.
- 2016

It is shown that the number of non-zero entries of any least-p-norm solution of the LCP(q,M) is less than or equal to the rank of M for any arbitrary matrix M and any number of sparse solutions for p∈(0,1) are sparse solutions. Expand

Analysis of the equivalence relationship between l0$l_{0}$-minimization and lp$l_{p}$-minimization

- Mathematics, Medicine
- Journal of inequalities and applications
- 2017

An analytic expression of p∗(A,b)$p-minimization is presented, which is formulated by the dimension of the matrix A∈Rm×n$A\in\mathbb{R}^{m\times n}$ and the eigenvalue of the Matrix ATA$A^{T}A, and the vector b∗Rm$b\in 𝕂Rm}^{ m} is presented. Expand

#### References

SHOWING 1-10 OF 10 REFERENCES

Approximation Algorithms for Combinatorial Problems

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1974

For the problem of finding the maximum clique in a graph, no algorithm has been found for which the ratio does not grow at least as fast as n^@e, where n is the problem size and @e>0 depends on the algorithm. Expand

Rank degeneracy and least squares problems

- Mathematics
- 1976

This paper is concerned with least squares problems when the least squares matrix A is near a matrix that is not of full rank. A definition of numerical rank is given. It is shown that under certain… Expand

Computers and Intractability: A Guide to the Theory of NP-Completeness

- Computer Science, Mathematics
- 1978

Horn formulae play a prominent role in artificial intelligence and logic programming. In this paper we investigate the problem of optimal compression of propositional Horn production rule knowledge… Expand

Sparse approximate multiquadric interpolation

- Mathematics
- 1994

Abstract Multiquadric interpolation is a technique for interpolating nonuniform samples of multivariate functions, in order to enable a variety of operations such as data visualization. We are… Expand

Computational geometry: an introduction

- Computer Science, Mathematics
- 1985

This book offers a coherent treatment, at the graduate textbook level, of the field that has come to be known in the last decade or so as computational geometry. Expand

Occam's razor for functions

- Computer Science
- COLT '93
- 1993

It is shown that the existence of an Om approximation is sufficient to guarantee the probably approximate learnability of classes of functions on the reals even in the presence of arbkwily large but random additive noise. Expand

Interpolation of scattered data: Distance matrices and conditionally positive definite functions

- Mathematics
- 1986

Among other things, we prove that multiquadric surface interpolation is always solvable, thereby settling a conjecture of R. Franke.

Information Theory and Reliable Communication

- Mathematics
- 1968

Communication Systems and Information Theory. A Measure of Information. Coding for Discrete Sources. Discrete Memoryless Channels and Capacity. The Noisy-Channel Coding Theorem. Techniques for Coding… Expand

Theory and applications of the multi-quadric biharmonic method

- Comput. Math. Appl
- 1990

The null space problem I

- Complexity, SIAM J. Alg. Disc. Meth
- 1986