This book provides an introduction to the mathematical and algorithmic foundations of data
science, including machine learning, high-dimensional geometry, and analysis of large …

Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately
estimate the mixture parameters. We give an algorithm for this problem that has running time …

There has been much progress on efficient algorithms for clustering data points generated
by a mixture of k probability distributions under the assumption that the means of the …

The question of polynomial learn ability of probability distributions, particularly Gaussian
mixture distributions, has recently received significant attention in theoretical computer …

Problems of clustering data from pairwise similarity information are ubiquitous in Computer
Science. Theoretical treatments typically view the similarity information as ground-truth and …

We present an extension of Principal Component Analysis (PCA) and a new algorithm for
clustering points in R n based on it. The key property of the algorithm is that it is affine …

Learning parameters from voluminous data can be prohibitive in terms of memory and
computational requirements. We propose a 'compressive learning'framework, where we …

Spectral methods refer to the use of eigenvalues, eigenvectors, singular values, and
singular vectors. They are widely used in Engineering, Applied Mathematics, and Statistics …

This book bridges theoretical computer science and machine learning by exploring what the
two sides can teach each other. It emphasizes the need for flexible, tractable models that …

In this paper, we initiate a theoretical study of the problem of clustering data under
interactive feedback. We introduce a query-based model in which users can provide …