Robust and Scalable Column/Row Sampling from Corrupted Big Data

Mostafa Rahmani, George K. Atia

Abstract

Conventional sampling techniques fall short of drawing descriptive sketches of the data when the data is grossly corrupted, as such corruptions break the low-rank structure required for them to perform satisfactorily. In this paper, we present new sampling algorithms which can locate the informative columns in the presence of severe data corruptions. In addition, we develop new scalable randomized designs of the proposed algorithms. The proposed approach is simultaneously robust to sparse corruption and outliers and substantially outperforms the state-of-the-art robust sampling algorithms as demonstrated by experiments conducted using both real and synthetic data.

Introduction

In the era of Big Data, the ability to select a small, representative subset of data points—a process known as column sampling—is essential for summarizing massive datasets, reducing memory overhead, and accelerating machine learning tasks like clustering and recommendation. However, traditional sampling algorithms face two critical challenges: sensitivity to data corruption and poor scalability. Most existing methods assume data is "clean" and follows a strict low-rank structure. When faced with sparse corruption (e.g., random pixel errors) or outliers (entirely irrelevant data points), these algorithms often fail because the noise breaks the linear dependencies they rely on. Furthermore, many robust algorithms require $O(N^3)$ operations, making them computationally prohibitive for datasets with millions of entries.

Methodology

To address these limitations, we propose a framework that combines robust convex optimization with randomized "sketching" techniques. Our approach formulates the sampling problem using $\ell_1$ and $\ell_{1,2}$ norms, which are mathematically designed to ignore sparse noise and outlying columns, focusing instead on the underlying low-rank structure.

Randomized Sketching and Subspace Pursuit

To achieve scalability, we introduce Randomized Sketching (Algorithm 1). Rather than processing the entire dataset, we "sketch" the data by randomly sampling a few rows to identify important columns. This reduces computational complexity from $O(N^3)$ to approximately $O(r^3 + r^2N)$, where $r$ is the rank of the data.

For highly structured data where both rows and columns are non-uniformly distributed, we developed the Column/Row Subspace Pursuit (Algorithm 2). This iterative method alternates between sampling rows and columns to converge on the most informative subset of the data.

Schematic representation of the iterative Column/Row Subspace Pursuit algorithm, illustrating the relationship between the full data matrix D and its sampled subsets.

Experimental Evaluation

We evaluated our algorithms using synthetic low-rank matrices, the Yale Face Database B (with 2% added synthetic noise), and video data from a cartoon movie. The results demonstrate that our method is significantly more robust than previous state-of-the-art approaches, such as Robust Exemplar Extraction.

In tests involving up to 600 outlying columns, our method consistently ignored the outliers and selected "inlier" data points. In contrast, competing algorithms began selecting outliers once a certain noise threshold was reached. Furthermore, the algorithm demonstrated exceptional efficiency; on a $2000 \times 6300$ matrix, it identified descriptive columns in just 2 to 3 iterations.

Performance analysis of the proposed method: (Left) Recovery error decreases as the number of sampled columns increases. (Right) The rank of sampled columns converges to the true rank within a few iterations.

Key Insights and Discussion

A primary insight of this work is that the row space of a matrix can be effectively captured using a small number of randomly sampled rows, even when the column distribution is highly non-uniform. This allows the algorithm to identify the "best" columns by analyzing only a tiny horizontal slice of the data. Unlike random sampling, which fails when data clusters are of vastly different sizes, our deterministic approach ensures that even small, rare clusters are represented in the final sample.

While the algorithm is highly effective, it does require an upper bound on the rank ($r$) of the clean data and involves regularization parameters ($\gamma, \lambda$) that may require tuning based on noise levels. Future work will explore applying this sketching approach to other classical data mining tools to enhance their robustness and scalability.

Conclusion

This paper introduces a robust and scalable framework for column and row sampling that remains accurate under heavy data corruption. By leveraging convex optimization and randomized sketching, we provide a solution that is both computationally efficient and resilient to outliers, offering a powerful tool for Big Data summarization and analysis.

Summary updated

Abstract

Conventional sampling techniques fall short of drawing descriptive sketches of the data when the data is grossly corrupted as such corruptions break the low rank structure required for them to perform satisfactorily. In this paper, we present new sampling algorithms which can locate the informative columns in presence of severe data corruptions. In addition, we develop new scalable randomized designs of the proposed algorithms. The proposed approach is simultaneously robust to sparse corruption and outliers and substantially outperforms the state-of-the-art robust sampling algorithms as demonstrated by experiments conducted using both real and synthetic data.
BibTeX
@inproceedings{rahmani2017robust,
  author = {Mostafa Rahmani and George K. Atia},
  title = {{Robust and Scalable Column/Row Sampling from Corrupted Big Data}},
  booktitle = {Workshops @ ICCV},
  year = {2017},
  url = {https://openreview.net/forum?id=rThEkT6-jBN},
}
Figure