We will present some results and some open problems related to shotgun assembly of graphs for random generating models.Shotgun assembly of graphs is the problem of recovering a random graph or a randomly labelled graphs from small pieces. This problem generalizes the theoretically elegant and practically important problem of shotgun assembly of DNA sequences. The…

Abstract: In sparse principal components analysis (PCA), the task is to infer a sparse, low-rank matrix from noisy observations. Johnstone and Lu proposed the popular “spiked covariance” model, wherein the population distribution is equivariant with the exception of a single direction, called the spike. Assuming that the spike direction is sparse in some basis, they…