Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Linear Equations
Necessary and Sufficient Condition
Optimal Solution
Linear Program
Subscribe
Academic
Publications
Probability of unique integer solution to a system of linear equations
Probability of unique integer solution to a system of linear equations,10.1016/j.ejor.2011.04.010,European Journal of Operational Research,O. L. Manga
Edit
Probability of unique integer solution to a system of linear equations
(
Citations: 4
)
BibTex

RIS

RefWorks
Download
O. L. Mangasarian
,
Benjamin Recht
We consider a system of m
linear equations
in n variables Ax=d and give necessary and sufficient conditions for the existence of a unique solution to the system that is integer: x∈{−1,1}n. We achieve this by reformulating the problem as a
linear program
and deriving necessary and sufficient conditions for the integer solution to be the unique primal optimal solution. We show that as long as m is larger than n/2, then the linear programming reformulation succeeds for most instances, but if m is less than n/2, the reformulation fails on most instances. We also demonstrate that these predictions match the empirical performance of the linear programming formulation to very high accuracy.
Journal:
European Journal of Operational Research  EJOR
, vol. 214, no. 1, pp. 2730, 2011
DOI:
10.1016/j.ejor.2011.04.010
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.sciencedirect.com
)
(
pages.cs.wisc.edu
)
Citation Context
(3)
...Related results [
7
] along those lines show that as long as the number of rows is greater than half the number of columns of A, and all sets of m columns of A are linearly independent with probability 1 and each column of A is symmetrically distributed around the origin, then with probability exceeding 1 ,...
O. L. Mangasarian
,
et al.
Uniqueness of integer solution of linear equations
...Given the eigenvalues of a matrix and additionally a few linear measurements of the matrix, when can we recover the matrix? When does a system of linear equations have a unique integer solution? This question is related to the integrality gap between a class of integer linear programs and their linearprogramming relaxations, and has previously been studied in [8], [
14
]...
...This corresponds to a version of the multiknapsack problem [
14
]...
...This agrees with results obtained in [8], [
14
]...
Venkat Chandrasekaran
,
et al.
The Convex algebraic geometry of linear inverse problems
...Also, it is interesting to note that if α → 1 then β → 1. This means that in binary compressed sensing one needs at most m = n measurements no matter how sparse the signal is (more on this phenomenon the interested reader can find in an excellent recent work [
20
])...
Mihailo Stojnic
.
Recovery thresholds for ℓ1 optimization in binary compressed sensing
References
(18)
An algorithm for the solution of the 01 knapsack problem
(
Citations: 51
)
D. Fayard
,
G. Plateau
Journal:
Computing
, 1982
On Sparse Representations in Arbitrary Redundant Bases
(
Citations: 177
)
JeanJacques Fuchs
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 50, no. 6, pp. 13411344, 2004
Probability inequalities for sums of bounded random variables
(
Citations: 449
)
W. Hoeffding
Published in 1962.
Introduction to Global Optimization
(
Citations: 316
)
R. Horst
,
P. M. Pardalos
,
N. V. Thoai
Published in 1995.
Knapsack feasibility as an absolute value equation solvable by successive linear programming
(
Citations: 8
)
O. L. Mangasarian
Journal:
Optimization Letters
, vol. 3, no. 2, pp. 161170, 2009
Sort by:
Citations
(4)
The Convex Geometry of Linear Inverse Problems
(
Citations: 3
)
Venkat Chandrasekaran
,
Benjamin Recht
,
Pablo A. Parrilo
,
Alan S. Willsky
Published in 2010.
Uniqueness of integer solution of linear equations
(
Citations: 2
)
O. L. Mangasarian
,
Michael C. Ferris
Journal:
Optimization Letters
, vol. 4, no. 4, pp. 559565, 2010
The Convex algebraic geometry of linear inverse problems
Venkat Chandrasekaran
,
Benjamin Recht
,
Pablo A. Parrilo
,
Alan S. Willsky
Conference:
Annual Allerton Conference on Communication, Control, and Computing  Allerton
, 2010
Recovery thresholds for ℓ1 optimization in binary compressed sensing
Mihailo Stojnic
Conference:
IEEE International Symposium on Information Theory  ISIT
, 2010