Using the eigenvalue relaxation for binary least-squares estimation problems
From MaRDI portal
Abstract: The goal of this paper is to survey the properties of the eigenvalue relaxation for least squares binary problems. This relaxation is a convex program which is obtained as the Lagrangian dual of the original problem with an implicit compact constraint and as such, is a convex problem with polynomial time complexity. Moreover, as a main pratical advantage of this relaxation over the standard Semi-Definite Programming approach, several efficient bundle methods are available for this problem allowing to address problems of very large dimension. The necessary tools from convex analysis are recalled and shown at work for handling the problem of exactness of this relaxation. Two applications are described. The first one is the problem of binary image reconstruction and the second is the problem of multiuser detection in CDMA systems.
Recommendations
- Least squares reconstruction of binary images using eigenvalue optimization
- Probabilistic Analysis of Semidefinite Relaxation for Binary Quadratic Minimization
- Just relax: convex programming methods for identifying sparse signals in noise
- SDP relaxation of homogeneous quadratic optimization: approximation bounds and applications
- Application of semi definite relaxation and variable neighborhood search for multiuser detection in synchronous CDMA
Cites work
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- A second-order bundle method to minimize the maximum eigenvalue function.
- A Spectral Bundle Method for Semidefinite Programming
- Applications of convex optimization in signal processing and digital communication
- Bounding the convergence time of the Gibbs sampler in Bayesian image restoration
- Convex Relaxations of (0, 1)-Quadratic Programming
- Derivatives and Perturbations of Eigenvectors
- Designing structured tight frames via an alternating projection method
- scientific article; zbMATH DE number 3986503 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 477581 (Why is no real title available?)
- scientific article; zbMATH DE number 1534297 (Why is no real title available?)
- scientific article; zbMATH DE number 1534299 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 1424225 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Laplacian eigenvalues and the maximum cut problem
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Minimum probability of error for asynchronous Gaussian multiple-access channels
- Nonpolyhedral Relaxations of Graph-Bisection Problems
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- SDP relaxations in combinatorial optimization from a Lagrangian viewpoint.
- Semidefinite programming for discrete optimization and matrix completion problems
- Semidefinite relaxation and nonconvex quadratic optimization
Cited in
(2)
This page was built for publication: Using the eigenvalue relaxation for binary least-squares estimation problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q839052)
