7 accepted papers
Lloyd's k-means algorithm is one of the most widely used clustering methods. We prove that in high-dimensional, high-noise settings, the algorithm exhibits catastrophic failure: with high probability, essentially every partition of the data is a fixed point. Consequently, Lloyd's algorithm simply re…
We study the problems of detection and recovery of hidden submatrices with elevated means inside a large Gaussian random matrix. We consider two different structures for the planted submatrices. In the first model, the planted matrices are disjoint, and their row and column indices can be arbitrary.…
We study the multi-target detection problem of recovering a target signal from a noisy measurement that contains multiple copies of the signal at unknown locations. Motivated by the structure reconstruction problem in cryo-electron microscopy, we focus on the high noise regime, where noise hampers a…
Motivated by the problem of determining the atomic structure of macromolecules using single-particle cryo-electron microscopy (cryo-EM), we study the sample and computational complexities of the sparse multi-reference alignment (MRA) model: the problem of estimating a sparse signal from its noisy, c…
We introduce a framework for recovering an image from its rotationally and translationally invariant features based on autocorrelation analysis. This work is an instance of the multi-target detection statistical model, which is mainly used to study the mathematical and computational properties of si…
The problem of recovering a signal from its power spectrum is called phase retrieval. This problem appears in a variety of scientific applications, such as ultra-short laser pulse characterization and diffraction imaging. However, the problem for one-dimensional signals is ill-posed as there is no o…
The problem of recovering a signal from its phaseless short-time Fourier transform (STFT) measurements arises in several applications, such as ultra-short pulse measurements and ptychography. The redundancy offered by the STFT enables unique recovery under mild conditions. We show that in some cases…