2015/10/30 by Hajek, Bruce, Wu, Yihong, Xu, Jiaming · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (stat.ML) #Probability (math.PR) #Social and Information Networks (cs.SI) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.1510.09219
The principal submatrix localization problem deals with recovering a K× K principal submatrix of elevated mean μ in a large n× n symmetric matrix subject to additive standard Gaussian noise. This problem serves as a prototypical example for community detection, in which the community corresponds to the support of the submatrix. The main result of this paper is that in the regime Ω(√(n)) ≤ K ≤ o(n), the support of the submatrix can be weakly recovered (with o(K) misclassification errors on average) by an optimized message passing algorithm if λ= μ2K2/n, the signal-to-noise ratio, exceeds 1/e. This extends a result by Deshpande and Montanari previously obtained for K=Θ(√(n)). In addition, the algorithm can be extended to provide exact recovery whenever information-theoretically possible and achieve the information limit of exact recovery as long as K ≥ (n)/(log n) ((1)/(8e) + o(1)). The total running time of the algorithm is O(n2log n). Another version of the submatrix localization problem, known as noisy biclustering, aims to recover a K1× K2 submatrix of elevated mean μ in a large n1× n2 Gaussian matrix. The optimized message passing algorithm and its analysis are adapted to the bicluster problem assuming Ω(√(ni)) ≤ Ki ≤ o(ni) and K1\asymp K2. A sharp information-theoretic condition for the weak recovery of both clusters is also identified.