Robust Low-Complexity Randomized Methods for Locating Outliers in Large Matrices
This paper examines the problem of locating outlier columns in a large, otherwise low-rank matrix, in settings where {}{the data} are noisy, or where the overall matrix has missing elements. We propose a randomized two-step inference framework, and establish sufficient conditions on the required sample complexities under which these methods succeed (with high probability) in accurately locating the outliers for each task. Comprehensive numerical experimental results are provided to verify the theoretical bounds and demonstrate the computational efficiency of the proposed algorithm.
Code (0)
등록된 구현이 없습니다.
Tasks
Computational EfficiencyMissing ElementsSimilar Papers 제목 키워드 기반
Randomized Greedy Algorithms and Composable Coreset for k-Center Clustering with Outliers
In this paper, we study the problem of {\em $k$-center clustering with outliers}. The problem has many important applications in real world, but the presence of outliers can significantly increase the computational compl…
ClusteringIdentifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling
This paper examines the problem of locating outlier columns in a large, otherwise low-rank, matrix. We propose a simple two-step adaptive sensing and inference approach and establish theoretical guarantees for its perfor…
Collaborative FilteringScalable and Robust Tensor Ring Decomposition for Large-scale Data
Tensor ring (TR) decomposition has recently received increased attention due to its superior expressive performance for high-order tensors. However, the applicability of traditional TR decomposition algorithms to real-wo…
Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams
In this paper, we introduce new algorithms for Principal Component Analysis (PCA) with outliers. Utilizing techniques from computational geometry, specifically higher-degree Voronoi diagrams, we navigate to the optimal s…
NavigateLocating a Small Cluster Privately
We present a new algorithm for locating a small cluster of points with differential privacy [Dwork, McSherry, Nissim, and Smith, 2006]. Our algorithm has implications to private data exploration, clustering, and removal …
Clustering