Robust PCA with compressed data

Wooseok Ha, Rina Foygel BarberNeurIPS 2015 · OpenReview

Introduction

In the era of big data, we frequently face a "data squeeze." Constraints on storage, communication bandwidth, or privacy requirements mean we often work with compressed versions of our original datasets. Standard Robust Principal Component Analysis (RPCA) is designed to take a data matrix and split it into two parts: a low-rank component (representing the main trends) and a sparse component (representing outliers or foreground objects). However, if we only have access to a compressed version of the data, traditional RPCA fails.

This paper introduces a robust framework for performing RPCA on data that has been significantly compressed. By using a convex optimization approach, the authors demonstrate that it is possible to accurately recover sparse outliers and the compressed low-rank structure of a dataset, with error bounds that scale predictably based on the level of compression.

The Challenge of Compressed RPCA

Standard RPCA splits a data matrix $D$ into a low-rank component $L$ and a sparse component $S$. But what if we only observe $Y = DC$, where $C$ is a compression matrix?

The authors tackle a fundamental question: Can we still separate the "signal" from the "outliers" if the data is already compressed? The challenge is that compression is a lossy process. While sparse components might be recoverable (akin to compressed sensing), the low-rank component $L$ becomes "unidentifiable"—we cannot know exactly what $L$ was, only how it looks after being multiplied by the compression matrix.

A Convex Optimization Approach

To solve this "Compressed RPCA" problem, the authors propose a convex optimization program.

Instead of trying to recover the original $L$, they aim to recover the sparse component $S$ and the compressed low-rank component $P = L \cdot C$. They minimize a cost function that balances three elements:

  1. Fidelity: How well the reconstruction matches the observed compressed data (Least Squares).
  2. Low-Rankness: Encouraged by the nuclear norm of $P$.
  3. Sparsity: Encouraged by the $\ell_1$ norm of $S$.

To ensure the low-rank and sparse parts don't get confused, they impose a constraint on the "spikiness" of $P$. A key insight is that this spikiness condition—crucial for RPCA to work—is largely preserved even after random compression. The framework is also highly robust, simultaneously accounting for additive noise, model misspecification, and missing data.

Key Results and Scaling Laws

The paper provides deterministic error bounds using the "Restricted Eigenvalue" property, showing that the reconstruction error scales naturally with the compression dimension $m$. Specifically, the authors proved that the total squared error is bounded by a term proportional to $\frac{d}{m} [r(n+m) + sn \log(nd)]$, where $r$ is rank and $s$ is sparsity.

Error scales linearly with compression ratio

Experimental results on synthetic data perfectly mirrored these theoretical predictions. As shown above, the error grows linearly relative to the compression ratio $d/m$. When $m=d$ (no compression), the results collapse back into the known bounds for standard RPCA.

Error scaling with rank and sparsity

Further simulations confirm that the total squared error also scales predictably with the rank of the underlying data and the proportion of sparse outliers across different dimensions and compression levels.

Beyond synthetic data, the researchers evaluated their method on a realistic simulation of chlorine concentration levels across a network of 166 sensors over 4,310 time points. In this sensor network test, the "Low-rank + Sparse" model achieved an 8–9% reduction in reconstruction error compared to a standard low-rank-only model. This proves that accounting for sparse outliers is beneficial even when the data is heavily compressed.

Limitations and Future Directions

While powerful, the framework has limitations. The most significant is the "L" problem: the original low-rank matrix $L$ cannot be uniquely recovered. Users must be satisfied with recovering the compressed version $LC$ or the column space of $L$. Additionally, the convex program relies on three tuning parameters ($\alpha, \nu, \lambda$) that may require careful cross-validation in practice.

Currently, this work focuses on batch processing. A promising future direction is adapting this method for streaming data (online learning), where data is compressed and processed on the fly as it arrives from sensors.

Summary updated

Abstract

The robust principal component analysis (RPCA) problem seeks to separate low-rank trends from sparse outlierswithin a data matrix, that is, to approximate a $n\times d$ matrix $D$ as the sum of a low-rank matrix $L$ and a sparse matrix $S$.We examine the robust principal component analysis (RPCA) problem under data compression, wherethe data $Y$ is approximately given by $(L + S)\cdot C$, that is, a low-rank $+$ sparse data matrix that has been compressed to size $n\times m$ (with $m$ substantially smaller than the original dimension $d$) via multiplication witha compression matrix $C$. We give a convex program for recovering the sparse component $S$ along with the compressed low-rank component $L\cdot C$, along with upper bounds on the error of this reconstructionthat scales naturally with the compression dimension $m$ and coincides with existing results for the uncompressedsetting $m=d$. Our results can also handle error introduced through additive noise or through missing data.The scaling of dimension, compression, and signal complexity in our theoretical results is verified empirically through simulations, and we also apply our method to a data set measuring chlorine concentration acrossa network of sensors, to test its performance in practice.
BibTeX
@inproceedings{ha2015robust,
  author = {Wooseok Ha and Rina Foygel Barber},
  title = {{Robust PCA with compressed data}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=HkZDFvb_bB},
}
Figure