PETRELS: Parallel Subspace Estimation and Tracking by Recursive Least Squares from Partial Observations

Abstract

Many real world data sets exhibit an embedding of low-dimensional structure in a high-dimensional manifold. Examples include images, videos and internet traffic data. It is of great significance to reduce the storage requirements and computational complexity when the data dimension is high. Therefore we consider the problem of reconstructing a data stream from a small subset of its entries, where the data is assumed to lie in a low-dimensional linear subspace, possibly corrupted by noise. We further consider tracking the change of the underlying subspace, which can be applied to applications such as video denoising, network monitoring and anomaly detection. Our problem can be viewed as a sequential low-rank matrix completion problem in which the subspace is learned in an on-line fashion. The proposed algorithm, dubbed Parallel Estimation and Tracking by REcursive Least Squares (PETRELS), first identifies the underlying low-dimensional subspace via a recursive procedure for each row of the subspace matrix in parallel with discounting for previous observations, and then reconstructs the missing entries via least-squares estimation if required. Numerical examples are provided for direction-of-arrival estimation and matrix completion, comparing PETRELS with state of the art batch algorithms.

submitted to IEEE Trans. Signal Processing. Part of the result was reported at ICASSP 2012 and won the best student paper award

References in corpus (1)

• A Singular Value Thresholding Algorithm for Matrix Completion

Cited by in corpus (18)

• Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
• Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors
• Total Variation Regularized Tensor RPCA for Background Subtraction from Compressive Measurements
• Changepoint detection for high-dimensional time series with missing data
• Dictionary Learning over Distributed Models
• Network Volume Anomaly Detection and Identification in Large-scale Networks based on Online Time-structured Traffic Tensor Tracking
• Static and Dynamic Robust PCA and Matrix Completion: A Review
• Online Low-Rank Tensor Subspace Tracking from Incomplete Data by CP Decomposition using Recursive Least Squares
• Provable Dynamic Robust PCA or Robust Subspace Tracking
• Provable Subspace Tracking from Missing Data and Matrix Completion
• Subspace Estimation from Incomplete Observations: A High-Dimensional Analysis
• Estimation of the sample covariance matrix from compressive measurements
• The Role of Principal Angles in Subspace Classification
• Federated Over-Air Subspace Tracking from Incomplete and Corrupted Data
• A Neuron as a Signal Processing Device
• Adaptive-Rate Sparse Signal Reconstruction With Application in Compressive Background Subtraction
• Robust On-line Matrix Completion on Graphs
• Provable Low Rank Phase Retrieval