Capturing the Denoising Effect of PCA via Compression Ratio

• URL: http://arxiv.org/abs/2204.10888v2
• Date: Mon, 22 Apr 2024 02:35:30 GMT
• Title: Capturing the Denoising Effect of PCA via Compression Ratio
• Authors: Chandra Sekhar Mukherjee, Nikhil Doerkar, Jiapeng Zhang,
• Abstract summary: Principal component analysis (PCA) is one of the most fundamental tools in machine learning. In this paper, we propose a novel metric called emphcompression ratio to capture the effect of PCA on high-dimensional noisy data. Building on this new metric, we design a straightforward algorithm that could be used to detect outliers.
• Score: 3.967854215226183
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Principal component analysis (PCA) is one of the most fundamental tools in machine learning with broad use as a dimensionality reduction and denoising tool. In the later setting, while PCA is known to be effective at subspace recovery and is proven to aid clustering algorithms in some specific settings, its improvement of noisy data is still not well quantified in general. In this paper, we propose a novel metric called \emph{compression ratio} to capture the effect of PCA on high-dimensional noisy data. We show that, for data with \emph{underlying community structure}, PCA significantly reduces the distance of data points belonging to the same community while reducing inter-community distance relatively mildly. We explain this phenomenon through both theoretical proofs and experiments on real-world data. Building on this new metric, we design a straightforward algorithm that could be used to detect outliers. Roughly speaking, we argue that points that have a \emph{lower variance of compression ratio} do not share a \emph{common signal} with others (hence could be considered outliers). We provide theoretical justification for this simple outlier detection algorithm and use simulations to demonstrate that our method is competitive with popular outlier detection tools. Finally, we run experiments on real-world high-dimension noisy data (single-cell RNA-seq) to show that removing points from these datasets via our outlier detection method improves the accuracy of clustering algorithms. Our method is very competitive with popular outlier detection tools in this task.

Related papers

• Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth [83.15263499262824]
  We prove that gradient descent converges to a solution that completely disregards the sparse structure of the input. We show how to improve upon Gaussian performance for the compression of sparse data by adding a denoising function to a shallow architecture. We validate our findings on image datasets, such as CIFAR-10 and MNIST.
  arXiv  Detail & Related papers  (2024-02-07T16:32:29Z)
• Learning-Augmented K-Means Clustering Using Dimensional Reduction [1.7243216387069678]
  We propose a solution to reduce the dimensionality of the dataset using Principal Component Analysis (PCA) PCA is well-established in the literature and has become one of the most useful tools for data modeling, compression, and visualization.
  arXiv  Detail & Related papers  (2024-01-06T12:02:33Z)
• ALPCAH: Sample-wise Heteroscedastic PCA with Tail Singular Value Regularization [17.771454131646312]
  Principal component analysis is a key tool in the field of data dimensionality reduction. This paper develops a PCA method that can estimate the sample-wise noise variances. It is done without distributional assumptions of the low-rank component and without assuming the noise variances are known.
  arXiv  Detail & Related papers  (2023-07-06T03:11:11Z)
• CoMadOut -- A Robust Outlier Detection Algorithm based on CoMAD [0.3749861135832073]
  Outliers play a significant role, since they bear the potential to distort the predictions of a machine learning algorithm on a given dataset. To address this problem, we propose the robust outlier detection algorithm CoMadOut. Our approach can be seen as a robust alternative for outlier detection tasks.
  arXiv  Detail & Related papers  (2022-11-23T21:33:34Z)
• Few-Shot Non-Parametric Learning with Deep Latent Variable Model [50.746273235463754]
  We propose Non-Parametric learning by Compression with Latent Variables (NPC-LV) NPC-LV is a learning framework for any dataset with abundant unlabeled data but very few labeled ones. We show that NPC-LV outperforms supervised methods on all three datasets on image classification in low data regime.
  arXiv  Detail & Related papers  (2022-06-23T09:35:03Z)
• Stochastic and Private Nonconvex Outlier-Robust PCA [11.688030627514532]
  Outlier-robust PCA seeks an underlying low-dimensional linear subspace from a dataset corrupted with outliers. We show that our methods involve our methods, which involve a geodesic descent and a novel convergence analysis. The main application method is an effectively private algorithm for outlier-robust PCA.
  arXiv  Detail & Related papers  (2022-03-17T12:00:47Z)
• Turning Channel Noise into an Accelerator for Over-the-Air Principal Component Analysis [65.31074639627226]
  Principal component analysis (PCA) is a technique for extracting the linear structure of a dataset. We propose the deployment of PCA over a multi-access channel based on the algorithm of gradient descent. Over-the-air aggregation is adopted to reduce the multi-access latency, giving the name over-the-air PCA.
  arXiv  Detail & Related papers  (2021-04-20T16:28:33Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Attentional-Biased Stochastic Gradient Descent [74.49926199036481]
  We present a provable method (named ABSGD) for addressing the data imbalance or label noise problem in deep learning. Our method is a simple modification to momentum SGD where we assign an individual importance weight to each sample in the mini-batch. ABSGD is flexible enough to combine with other robust losses without any additional cost.
  arXiv  Detail & Related papers  (2020-12-13T03:41:52Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  Local features provide region-to-region rather than point-to-point correspondences. We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline. Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
  arXiv  Detail & Related papers  (2020-07-20T12:07:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.