Robust Subspace Recovery | Paris Giampouras

High-dimensional observations often lie near a low-dimensional subspace, but outliers can make that structure difficult to recover. I study algorithms that recover the underlying representation while also identifying its dimension.

Recovering a subspace of unknown dimension

Our ICLR 2022 work studies Dual Principal Component Pursuit (DPCP), which estimates directions orthogonal to the underlying subspace. By relaxing orthogonality constraints and using random initialization, multiple projected subgradient iterations can recover a sufficiently diverse collection of these directions.

Under the paper’s assumptions, this collection spans the subspace’s orthogonal complement with high probability. The algorithm therefore reveals the unknown codimension through its implicit regularization, connecting robust representation learning with optimization geometry.

Subspace recovered by the proposed projected subgradient approach

Orthogonal DPCP (left) and the proposed approach for unknown codimension (right).

Selected publication

Paris Giampouras, Benjamin Haeffele, and René Vidal. Implicit Bias of Projected Subgradient Method Gives Provable Robust Recovery of Subspaces of Unknown Codimension. ICLR 2022, spotlight.