Farzad Parvaresh

Mihailo Stojnic, Farzad Parvaresh, Babak Hassibi

Let A be an M by N matrix (M < N) which is an instance of a real random Gaussian ensemble. In compressed sensing we are interested in finding the sparsest solution to the system of equations A x = y for a given y. In general, whenever the sparsity of x is smaller than half the dimension of y then with overwhelming probability over A the sparsest solution is unique and can be found by an exhaustive search over x with an exponential time complexity for any y. The recent work of Candés, Donoho, and Tao shows that minimization of the L_1 norm of x subject to A x = y results in the sparsest solution provided the sparsity of x, say K, is smaller than a certain threshold for a given number of measurements. Specifically, if the dimension of y approaches the dimension of x, the sparsity of x should be K < 0.239 N. Here, we consider the case where x is d-block sparse, i.e., x consists of n = N / d blocks where each block is either a zero vector or a nonzero vector. Instead of L_1-norm relaxation, we consider the following relaxation min x \| X_1 \|_2 + \| X_2 \|_2 + ... + \| X_n \|_2, subject to A x = y where X_i = (x_{(i-1)d+1}, x_{(i-1)d+2}, ..., x_{i d}) for i = 1,2, ..., N. Our main result is that as n -> \infty, the minimization finds the sparsest solution to Ax = y, with overwhelming probability in A, for any x whose block sparsity is k/n < 1/2 - O(ε), provided M/N > 1 - 1/d, and d = Ω(\log(1/ε)/ε). The relaxation can be solved in polynomial time using semi-definite programming.

Amir R. Asadi, Akbar Davoodi, Ramin Javadi et al.

Community detection in networks is a fundamental problem in machine learning and statistical inference, with applications in social networks, biological systems, and communication networks. The stochastic block model (SBM) serves as a canonical framework for studying community structure, and exact recovery, identifying the true communities with high probability, is a central theoretical question. While classical results characterize the phase transition for exact recovery based solely on graph connectivity, many real-world networks contain additional data, such as node attributes or labels. In this work, we study exact recovery in the Data Block Model (DBM), an SBM augmented with node-associated data, as formalized by Asadi, Abbe, and Verdú (2017). We introduce the Chernoff--TV divergence and use it to characterize a sharp exact recovery threshold for the DBM. We further provide an efficient algorithm that achieves this threshold, along with a matching converse result showing impossibility below the threshold. Finally, simulations validate our findings and demonstrate the benefits of incorporating vertex data as side information in community detection.