text: Consider an Erd "os-Renyi random graph in which each edge is present independently with probability 1 2, except for a subset @math of the vertices that form a clique (a completely connected subgraph). We consider the problem of identifying the clique, given a realization of such a random graph. The best known algorithm provably finds the clique in linear time with high probability, provided @math dekel2011finding . Spectral methods can be shown to fail on cliques smaller than @math . In this paper we describe a nearly linear time algorithm that succeeds with high probability for @math for any @math . This is the first algorithm that provably improves over spectral methods. We further generalize the hidden clique problem to other background graphs (the standard case corresponding to the complete graph on @math vertices). For large girth regular graphs of degree @math we prove that local' algorithms succeed if @math and fail if @math .
  @cite_7: We consider the problem of estimating a rank-one matrix in Gaussian noise under a probabilistic model for the left and right factors of the matrix. The probabilistic model can impose constraints on the factors including sparsity and positivity that arise commonly in learning problems. We propose a simple iterative procedure that reduces the problem to a sequence of scalar estimation computations. The method is similar to approximate message passing techniques based on Gaussian approximations of loopy belief propagation that have been used recently in compressed sensing. Leveraging analysis methods by Bayati and Montanari, we show that the asymptotic behavior of the estimates from the proposed iterative procedure is described by a simple scalar equivalent model, where the distribution of the estimates is identical to certain scalar estimates of the variables in Gaussian noise. Moreover, the effective Gaussian noise level is described by a set of state evolution equations. The proposed method thus provides a computationally simple and general method for rank-one estimation problems with a precise analysis in certain high-dimensional settings.
  @cite_36: “Approximate message passing” (AMP) algorithms have proved to be effective in reconstructing sparse signals from a small number of incoherent linear measurements. Extensive numerical experiments further showed that their dynamics is accurately tracked by a simple one-dimensional iteration termed state evolution. In this paper, we provide rigorous foundation to state evolution. We prove that indeed it holds asymptotically in the large system limit for sensing matrices with independent and identically distributed Gaussian entries. While our focus is on message passing algorithms for compressed sensing, the analysis extends beyond this setting, to a general class of algorithms on dense graphs. In this context, state evolution plays the role that density evolution has for sparse graphs. The proof technique is fundamentally different from the standard approach to density evolution, in that it copes with a large number of short cycles in the underlying factor graph. It relies instead on a conditioning technique recently developed by Erwin Bolthausen in the context of spin glass theory.
  @cite_9: This paper studies the estimation of a high-dimensional vector signal where the observation is a known "sparse" linear transformation of the signal corrupted by additive Gaussian noise. A paradigm of such a linear system is code-division multiple access (CDMA) channel with sparse spreading matrix. Assuming a "semi-regular" ensemble of sparse matrix linear transformations, where the bi-partite graph describing the system is asymptotically cycle-free, it is shown that belief propagation (BP) achieves the minimum mean-square error (MMSE) in estimating the transformation of the input vector in the large-system limit. The result holds regardless of the the distribution and power of the input symbols. Furthermore, the mean squared error of estimating each symbol of the input vector using BP is proved to be equal to the MMSE of estimating the same symbol through a scalar Gaussian channel with some degradation in the signal-to-noise ratio (SNR). The degradation, called the efficiency, is determined from a fixed-point equation due to Guo and Verdu, which is a generalization of Tanaka's formula to arbitrary prior distributions.
  @cite_24: We consider the CDMA (code-division multiple-access) multi-user detection problem for binary signals and additive white gaussian noise. We propose a spreading sequences scheme based on random sparse signatures, and a detection algorithm based on belief propagation (BP) with linear time complexity. In the new scheme, each user conveys its power onto a finite number of chips l, in the large system limit. We analyze the performances of BP detection and prove that they coincide with the ones of optimal (symbol MAP) detection in the l → ∞ limit. In the same limit, we prove that the information capacity of the system converges to Tanaka's formula for random 'dense' signatures, thus providing the first rigorous justification of this formula. Apart from being computationally convenient, the new scheme allows for optimization in close analogy with irregular low density parity check code ensembles.
  @cite_15: We consider a class of nonlinear mappings FA,N in R N indexed by symmetric random matrices A ∈ R N×N with independent entries. Within spin glass theory, special cases of these mappings correspond to iterating the TAP equations and were studied by Erwin Bolthausen. Within information theory, they are known as ‘approximate message passing’ algorithms. We study the high-dimensional (large N) behavior of the iterates of F for polynomial functions F, and prove that it is universal, i.e. it depends only on the first two moments of the entries of A, under a subgaussian tail condition. As an application, we prove the universality of a certain phase transition arising in polytope geometry and compressed sensing. This solves –for a broad class of random projections– a conjecture by David Donoho and Jared Tanner.
  @cite_13: Compressed sensing aims to undersample certain high-dimensional signals yet accurately reconstruct them by exploiting signal characteristics. Accurate reconstruction is possible when the object to be recovered is sufficiently sparse in a known basis. Currently, the best known sparsity–undersampling tradeoff is achieved when reconstructing by convex optimization, which is expensive in important large-scale applications. Fast iterative thresholding algorithms have been intensively studied as alternatives to convex optimization for large-scale problems. Unfortunately known fast algorithms offer substantially worse sparsity–undersampling tradeoffs than convex optimization. We introduce a simple costless modification to iterative thresholding making the sparsity–undersampling tradeoff of the new algorithms equivalent to that of the corresponding convex optimization procedures. The new iterative-thresholding algorithms are inspired by belief propagation in graphical models. Our empirical measurements of the sparsity–undersampling tradeoff for the new algorithms agree with theoretical calculations. We show that a state evolution formalism correctly derives the true sparsity–undersampling tradeoff. There is a surprising agreement between earlier calculations based on random convex polytopes and this apparently very different theoretical formalism.
summary: The algorithm we introduce for the case @math is analogous to the linearized BP' algorithm of @cite_24 @cite_9 , and to the approximate message passing (AMP) algorithm of @cite_13 @cite_36 @cite_15 . These ideas have been applied to low-rank approximation in @cite_7 . The present setting poses however several technical challenges with respect to earlier work in this area: @math The entries of the data matrix are not i.i.d.; @math They are non-Gaussian with --in general-- non-zero mean; @math We seek exact recovery instead of estimation; @math The sparsity set @math to be reconstructed scales sublinearly with @math .