PETRELS: Subspace estimation and tracking from partial observations

We consider the problem of reconstructing a data stream from a small subset of its entries, where the data stream is assumed to lie in a low-dimensional linear subspace, possibly corrupted by noise. It is also important to track the change of underlying subspace for many applications. This problem can be viewed as a sequential low-rank matrix completion problem in which the subspace is learned in an online fashion. The proposed algorithm, called Parallel Estimation and Tracking by REcursive Least Squares (PETRELS), identifies the underlying low-dimensional subspace via a recursive procedure for each row of the subspace matrix in parallel, and then reconstructs the missing entries via least-squares estimation if required. PETRELS outperforms previous approaches by discounting observations in order to capture long-term behavior of the data stream and be able to adapt to it. Numerical examples are provided for direction-of-arrival estimation and matrix completion, comparing PETRELS with state of the art batch algorithms.