Convergence of the Huber Regression M-Estimate in the Presence of Dense Outliers

in IEEE Signal Processing Letters (2014), 21(11), 1211-1214

We consider the problem of estimating a deterministic unknown vector which depends linearly on noisy measurements, additionally contaminated with (possibly unbounded) additive outliers. The measurement ... [more ▼]

We consider the problem of estimating a deterministic unknown vector which depends linearly on noisy measurements, additionally contaminated with (possibly unbounded) additive outliers. The measurement matrix of the model (i.e., the matrix involved in the linear transformation of the sought vector) is assumed known, and comprised of standard Gaussian i.i.d. entries. The outlier variables are assumed independent of the measurement matrix, deterministic or random with possibly unknown distribution. Under these assumptions we provide a simple proof that the minimizer of the Huber penalty function of the residuals converges to the true parameter vector with a root n-rate, even when outliers are dense, in the sense that there is a constant linear fraction of contaminated measurements which can be arbitrarily close to one. The constants influencing the rate of convergence are shown to explicitly depend on the outlier contamination level. [less ▲]

Semidefinite Relaxations of Robust Binary Least Squares under Ellipsoidal Uncertainty Sets

in IEEE Transactions on Signal Processing (2011), 59(11), 5169-5180

The problem of finding the least squares solution s to a system of equations Hs = y is considered, when s is a vector of binary variables and the coefficient matrix H is unknown but of bounded uncertainty ... [more ▼]

The problem of finding the least squares solution s to a system of equations Hs = y is considered, when s is a vector of binary variables and the coefficient matrix H is unknown but of bounded uncertainty. Similar to previous approaches to robust binary least squares, we explore the potential of a min-max design with the aim to provide solutions that are less sensitive to the uncertainty in H. We concentrate on the important case of ellipsoidal uncertainty, i.e., the matrix H is assumed to be a deterministic unknown quantity which lies in a given uncertainty ellipsoid. The resulting problem is NP-hard, yet amenable to convex approximation techniques: Starting from a convenient reformulation of the original problem, we propose an approximation algorithm based on semidefinite relaxation that explicitly accounts for the ellipsoidal uncertainty in the coefficient matrix. Next, we show that it is possible to construct a tighter relaxation by suitably changing the description of the feasible region of the problem, and formulate an approximation algorithm that performs better in practice. Interestingly, both relaxations are derived as Lagrange bidual problems corresponding to the two equivalent problem reformulations. The strength of the proposed tightened relaxation is demonstrated by pertinent simulations. [less ▲]

The Error Probability of the Fixed-Complexity Sphere Decoder

in IEEE Transactions on Signal Processing (2009), 57(7), 2711-2720

Download Citation Email Print Request Permissions Save to Project The fixed-complexity sphere decoder (FSD) has been previously proposed for multiple-input multiple-output (MIMO) detection in order to ... [more ▼]

Download Citation Email Print Request Permissions Save to Project The fixed-complexity sphere decoder (FSD) has been previously proposed for multiple-input multiple-output (MIMO) detection in order to overcome the two main drawbacks of the sphere decoder (SD), namely its variable complexity and its sequential structure. Although the FSD has shown remarkable quasi-maximum-likelihood (ML) performance and has resulted in a highly optimized real-time implementation, no analytical study of its performance existed for an arbitrary MIMO system. Herein, the error probability of the FSD is analyzed, proving that it achieves the same diversity as the maximum-likelihood detector (MLD) independent of the constellation used. In addition, it can also asymptotically yield ML performance in the high-signal-to-noise ratio (SNR) regime. Those two results, together with its fixed complexity, make the FSD a very promising algorithm for uncoded MIMO detection. [less ▲]

The Diversity Order of the Semidefinite Relaxation Detector

in IEEE Transactions on Information Theory (2008), 54(4), 14061422

Full Diversity Detection in MIMO Systems with a Fixed-Complexity Sphere Decoder

in Proceedings IEEE International Conference on Acoustics, Speech, and Signal Processing (2007)

On the Complexity of Sphere Decoding in Digital Communications

in IEEE Transactions on Signal Processing (2005), 53