Sparse Principal Component of a Rank-deficient Matrix
[Asteris, Papailiopoulos, Karysinos]
Where? 2011 ISIT (submitted)
What we do? We prove that the K-sparse principal component of a positive semidefinite matrix C is polynomially solvable when the NxN matrix can be written as
C = UU’+σI
and U has rank D that is not a function of N. The complexity of our rank-D optimal algorithm is O(N^(D+1)).
In our algorithmic developments, we exploit the use of auxiliary spherical variables that unlock the low rank structure of matrix U and a polynomial number of easy local problems is solved.
Download: ISIT
MCMC Methods for Integer Least-Squares Problems
[Hassibi, Papailiopoulos, Dimakis]
Where? 2010 Allerton
What we do? We use a “heat bath” version of MCMC and show that there is a trade-off between the mixing time of the Markov chain and how long it takes for the algorithm to find the optimal solution once the chain has mixed. We consider some interesting SNR regimes where the MC, on average, converges in polynomial time to the stationary distribution and the MIMO detection problem of interest can be efficiently solved.
Download: allerton
Maximum-likelihood noncoherent OSTBC detection with polynomial complexity
[Papailiopoulos, Karysinos]
Where? partial results at 2008 Allerton and 2009 Asilomar, published in IEEE TW.
What we do? We consider the problem of blind detection of data that are encoded using orthogonal space time codes, like the Alamouti code. We prove that the complexity to solve the detection problem is polynomially solvable under some sufficient conditions.
Download: allerton, asilomar, TW, slides.
Polynomial-complexity maximum-likelihood block noncoherent MPSK detection
[Papailiopoulos, Karysinos]
Where? 2008 ICASSP.
What we do? Here we prove that the optimal blind detection of MPSK symbol vectors is equivalent to the problem of finding of the M-phase vector that maximizes a rank-deficient quadratic form, which we solved in the previous paper ^.^
Download: icassp
Efficient computation of the M-phase vector that maximizes a rank-deficient quadratic form
[Papailiopoulos, Karysinos]
Where? 2008 CISS.
What we do? We consider the problem
max x’AA’x
where x is an M-PSK vector of length N. We prove that this combinatorial problem, although NP-hard in the general case, can be solved in time polynomial when A has fixed rank D.
The complexity of our approach is O((MN)^(2D)) compared to the brute force M^N steps that an exhaustive search would take.
Near ML detection of nonlinearly distorted OFDM signals
[Papailiopoulos, Karysinos]
Where? 2007 Asilomar.
What we do? So this is my first paper :). Here, we consider the problem of detecting OFDM signals that pass through a power amplifier. Interestingly, when considering nonlinear amplifiers, symbol-by-symbol detectors are not BER optimal. We develop an algorithm that operates on sequences of symbols and examines a set of locally optimal candidate data vectors. It seems that our scheme has a great benefit compared to single shot manner detectors, or other approaches.
