About
Consider the following linear model:
where
- H is a real or complex mixing matrix of dimensions m by n
- s is a state vector of dimensions n by 1
- y is an observation vector of dimensions m by 1
- v is a real or complex random vector with Gaussian, zero-mean, unit variance entries
- rho is quality of observation y (signal-to-noise ratio)
Integer Least Squares problem (Maximum-Likelihood detection) is given by:
where C^n is a given discrete set (constellation). Integer Least Squares problem is, in general, (strongly) NP-hard. Exhaustive search over all possible vectors s from C^n can be used to solve the problem with exponential complexity. In many practical scenarios a suboptimal strategy with reduced complexity is desired. This website is dedicated to efficient implementations of suboptimal strategies based on semi-definite relaxation of the original ML problem. The software presented on the website delivers near-ML probability of error with polynomial running time.
SDR Detector is based on a convex semifinite relaxation of the Integer Least Squares problem for binary and lattice constellations (BPSK, QPSK, (2^M)-PAM, (2^2M)-QAM, M > 0) and provides the following guarantees:
- theoretically proven worst-case polynomial complexity: O(n^3.5)
- exact solution with high probability
- constant factor approximation algorithm for the Integer Least Squares problem
- exact solution for a given channel realization with sufficiently high signal-to-noise ratio
PSK Detector is based on a low-rank (non-convex) semidefinite relaxation of the Integer Least Squares problem for binary, circular and lattice constellations (BPSK, QPSK, M-PSK, (2^2M)-QAM) and provides the following guarantees:
- theoretically proven worst case quadratic complexity: O(n^2)
- exact solution with high probability
- every local minimizer of the relaxed problem is 0.5-minimizer for M-PSK, M > 2 constellations
- every local minimizer is the global minimizer for BPSK (2-PSK) constellation
|
