Robust Kronecker Component Analysis

Mehdi Bahri, Yannis Panagakis, Stefanos Zafeiriou

Abstract

Dictionary learning and component analysis models are fundamental for learning compact representations that are relevant to a given task (feature extraction, dimensionality reduction, denoising, etc.). The model complexity is encoded by means of specific structure, such as sparsity, low-rankness, or nonnegativity. Unfortunately, approaches like K-SVD - that learn dictionaries for sparse coding via Singular Value Decomposition (SVD) - are hard to scale to high-volume and high-dimensional visual data, and fragile in the presence of outliers. Conversely, robust component analysis methods such as the Robust Principal Component Analysis (RPCA) are able to recover low-complexity (e.g., low-rank) representations from data corrupted with noise of unknown magnitude and support, but do not provide a dictionary that respects the structure of the data (e.g., images), and also involve expensive computations. In this paper, we propose a novel Kronecker-decomposable component analysis model, coined as Robust Kronecker Component Analysis (RKCA), that combines ideas from sparse dictionary learning and robust component analysis. RKCA has several appealing properties, including robustness to gross corruption; it can be used for low-rank modeling, and leverages separability to solve significantly smaller problems. We design an efficient learning algorithm by drawing links with a restricted form of tensor factorization, and analyze its optimality and low-rankness properties. The effectiveness of the proposed approach is demonstrated on real-world applications, namely background subtraction and image denoising and completion, by performing a thorough comparison with the current state of the art.

Introduction

Modern data is often high-dimensional and structured as tensors (multi-way arrays). Traditional methods for analyzing this data face a "double bind": they either struggle with scalability or lack robustness to outliers. Standard "flat" methods like PCA or K-SVD often ignore the multi-dimensional structure of images, leading to massive computational costs and a loss of spatial correlation. Furthermore, most dictionary learning techniques are fragile; a few "bad" pixels (outliers) or missing values can completely derail the model.

While Robust PCA (RPCA) was designed to handle outliers, it doesn't learn a structured dictionary that respects the inherent separability of data (e.g., the distinct horizontal and vertical dimensions of an image). Robust Kronecker Component Analysis (RKCA) bridges this gap by providing a framework for learning compact, low-rank representations of tensor data that is resilient to heavy noise and outliers.

Methodology

The core of RKCA is a structured tensor factorization model defined as $\mathcal{X} = \mathcal{R} \times_1 \mathbf{A} \times_2 \mathbf{B} + \mathcal{E}$.

The RKCA model decomposes a corrupted tensor into a structured low-rank component (via factors A, B, and core R) and a sparse error term E.
  • Separability: Instead of one giant dictionary, the model learns two smaller bases ($\mathbf{A}$ and $\mathbf{B}$) whose Kronecker product forms the full dictionary. This "separable" approach drastically reduces the number of parameters and allows for processing high-resolution images that would otherwise exceed memory limits.
  • Robustness: A sparse error term ($\mathcal{E}$) explicitly captures gross corruption, such as "salt and pepper" noise or occlusions, separating it from the clean, low-rank signal.
  • Optimization: The authors derive efficient solvers using the Alternating Direction of Multipliers Method (ADMM). To handle large-scale data, they introduce a Linearized ADMM (LADMM) variant that avoids solving expensive sub-problems.
  • Global Optimality: A major theoretical contribution is proving that for certain "degree 3" regularizers, this non-convex optimization problem actually has no spurious local minima—meaning any local solution found by the algorithm is a global optimum.

Experimental Setup

The model was evaluated across several diverse benchmarks to verify its versatility:

  • Synthetic Data: Used to verify the algorithm's ability to recover exact ranks and handle varying noise densities.
  • Background Subtraction: The Highway and Airport Hall video datasets, where the goal is to separate a static background from moving foreground objects.
  • Monochromatic Face Denoising: The Extended Yale-B dataset, consisting of face images under 64 different lighting conditions.
  • Color Image Denoising: The Facade image, chosen for its complex geometric patterns.
  • Image Completion: The 300 Faces in the Wild (300W) dataset, used to test the model's ability to "fill in" missing parts of faces caused by occlusions.

Analysis and Results

RKCA leverages structure as a form of regularization. It doesn't just rely on mathematical penalties (like the nuclear norm) to enforce low-rankness; it uses the factorized structure of the model itself to bound the rank, making it more "informed" than generic methods.

Singular value spectra of the learned factor matrices A and B, demonstrating the low-rank property of the RKCA representation.

Key results from the evaluation include:

  • Superior Denoising: In extreme noise conditions (e.g., 60% corruption), RKCA significantly outperformed state-of-the-art tensor methods (like HORPCA and TRPCA) in both visual quality and quantitative metrics (PSNR and FSIM).
  • Robust Background Subtraction: On the challenging Airport Hall dataset, RKCA achieved a top-tier AUC score of 0.88, proving highly effective at ignoring "ghosting" artifacts from immobile people.
  • Face Completion: RKCA was the only method among those tested that could successfully reconstruct faces with large self-occlusions in the 300W dataset, where standard matrix-based completion failed.

Conclusion and Future Work

RKCA offers a scalable and theoretically grounded way to denoise, complete, and analyze high-dimensional visual data. While the "degree 2" regularizer is the most practical, the authors acknowledge that the "global optimality" proof currently only applies to the more complex "degree 3" version. Future directions include adapting the model for supervised tasks like classification, exploring non-convex $L_p$ "pseudo-norms," and integrating the robust, multi-way tensor structure into deep auto-encoders.

Summary updated

Abstract

Dictionary learning and component analysis models are fundamental for learning compact representations that are relevant to a given task (feature extraction, dimensionality reduction, denoising, etc.). The model complexity is encoded by means of specific structure, such as sparsity, low-rankness, or nonnegativity. Unfortunately, approaches like K-SVD - that learn dictionaries for sparse coding via Singular Value Decomposition (SVD) - are hard to scale to high-volume and high-dimensional visual data, and fragile in the presence of outliers. Conversely, robust component analysis methods such as the Robust Principal Component Analysis (RPCA) are able to recover low-complexity (e.g., low-rank) representations from data corrupted with noise of unknown magnitude and support, but do not provide a dictionary that respects the structure of the data (e.g., images), and also involve expensive computations. In this paper, we propose a novel Kronecker-decomposable component analysis model, coined as Robust Kronecker Component Analysis (RKCA), that combines ideas from sparse dictionary learning and robust component analysis. RKCA has several appealing properties, including robustness to gross corruption; it can be used for low-rank modeling, and leverages separability to solve significantly smaller problems. We design an efficient learning algorithm by drawing links with a restricted form of tensor factorization, and analyze its optimality and low-rankness properties. The effectiveness of the proposed approach is demonstrated on real-world applications, namely background subtraction and image denoising and completion, by performing a thorough comparison with the current state of the art.
BibTeX
@article{bahri2019robust,
  author = {Mehdi Bahri and Yannis Panagakis and Stefanos Zafeiriou},
  title = {{Robust Kronecker Component Analysis}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2019},
  url = {https://openreview.net/forum?id=7nHICZ8i-4},
}
Figure