Robust iterative fitting of multilinear models based on linear programming

PARAllel FACtor (PARAFAC) analysis is an extension of low-rank matrix decomposition to higher-way arrays. It decomposes a given array in a sum of multilinear terms. PARAFAC analysis generalizes and unifies common array processing models (like joint diagonalization and ESPRIT); it has found numerous applications from blind multiuser detection and multi-dimensional harmonic retrieval, to clustering and nuclear magnetic resonance. The prevailing fitting algorithm in all these applications is based on alternating least squares (ALS) optimization, which is matched to Gaussian noise. In many cases, however, measurement errors are far from being Gaussian. In this paper, we develop an iterative algorithm for least absolute error fitting of general multilinear models, based on efficient interior point methods for Linear Programming (LP). We also benchmark its performance in Laplacian, Cauchy, and Gaussian noise environments, versus the respective CRBs and the commonly used ALS algorithm.