We analyze a compression scheme for large data sets that randomly keeps a small percentage of the components of each data sample. The benefit is that the output is a sparse matrix, and therefore, subsequent processing, such as principal component analysis (PCA) or K-means, is significantly faster, especially in a distributed-data setting. Furthermore, the sampling is single-pass and applicable to streaming data. The sampling mechanism is a variant of previous methods proposed in the literature combined with a randomized preconditioning to smooth the data. We provide guarantees for PCA in terms of the covariance matrix, and guarantees for K-means in terms of the error in the center estimators at a given step. We present numerical evidence to show both that our bounds are nearly tight and that our algorithms provide a real benefit when applied to standard test data sets, as well as providing certain benefits over related sampling approaches.

Generating low-rank approximations of kernel matrices that arise in nonlinear machine learning techniques holds the potential to significantly alleviate the memory and computational burdens. A compelling approach centers on finding a concise set of exemplars or landmarks to reduce the number of similarity measure evaluations from quadratic to linear concerning the data size. However, a key challenge is to regulate tradeoffs between the quality of landmarks and resource consumption. Despite the volume of research in this area, current understanding is limited regarding the performance of landmark selection techniques in the presence of class-imbalanced data sets that are becoming increasingly prevalent in many applications. Hence, this paper provides a comprehensive empirical investigation using several real-world imbalanced data sets, including scientific data, by evaluating the quality of approximate low-rank decompositions and examining their influence on the accuracy of downstream tasks. Furthermore, we present a new landmark selection technique called Distance-based Importance Sampling and Clustering (DISC), in which the relative importance scores are computed for improving accuracy-efficiency tradeoffs compared to existing works that range from probabilistic sampling to clustering methods. The proposed landmark selection method follows a coarse-to-fine strategy to capture the intrinsic structure of complex data sets, allowing us to substantially reduce the computational complexity and memory footprint with minimal loss in accuracy.

This study focuses on the estimation of the sample covariance matrix from low‐dimensional random projections of data known as compressive measurements. In particular, the authors present an unbiased estimator to extract the covariance structure from compressive measurements obtained by a general class of random projection matrices consisting of independent and identically distributed zero‐mean entries and finite first four moments. In contrast to previous works, they make no structural assumptions about the underlying covariance matrix such as being low‐rank. In fact, their analysis is based on a non‐Bayesian data setting which requires no distributional assumptions on the set of data samples. Furthermore, inspired by the generality of the projection matrices, they propose an approach to covariance estimation that utilises sparse Rademacher matrices. Therefore, their algorithm can be used to estimate the covariance matrix in applications with limited memory and computation power at the acquisition devices. Experimental results demonstrate that their approach allows for accurate estimation of the sample covariance matrix on several real‐world data sets including video data.