Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems

Given a large data matrix $Ainmathbb{R}^{ntimes n}$, we consider the problem of determining whether its entries are i.i.d. with some known marginal distribution $A_{ij}sim P_0$, or instead $A$ contains a principal submatrix $A_{{sf Q},{sf Q}}$ whose entries have marginal distribution $A_{ij}sim P_1 eq P_0$. As a special case, the hidden (or planted) clique problem requires to find a planted clique in an otherwise uniformly random graph. Assuming unbounded computational resources, this hypothesis testing problem is statistically solvable provided $|{sf Q}|ge C log n$ for a suitable constant $C$. However, despite substantial effort, no polynomial time algorithm is known that succeeds with high probability when $|{sf Q}| = o(sqrt{n})$. Recently Meka and Wigderson cite{meka2013association}, proposed a method to establish lower bounds within the Sum of Squares (SOS) semidefinite hierarchy. Here we consider the degree-$4$ SOS relaxation, and study the construction of cite{meka2013association} to prove that SOS fails unless $kge C, n^{1/3}/log n$. An argument presented by Barak implies that this lower bound cannot be substantially improved unless the witness construction is changed in the proof. Our proof uses the moments method to bound the spectrum of a certain random association scheme, i.e. a symmetric random matrix whose rows and columns are indexed by the edges of an Erdos-Renyi random graph.

Information-theoretically Optimal Sparse PCA

Sparse Principal Component Analysis (PCA) is a dimensionality reduction technique wherein one seeks a low-rank representation of a data matrix with additional sparsity constraints on the obtained representation. We consider two probabilistic formulations of sparse PCA: a spiked Wigner and spiked Wishart (or spiked covariance) model. We analyze an Approximate Message Passing (AMP) algorithm to estimate the underlying signal and show, in the high dimensional limit, that the AMP estimates are information-theoretically optimal. As an immediate corollary, our results demonstrate that the posterior expectation of the underlying signal, which is often intractable to compute, can be obtained using a polynomial-time scheme. Our results also effectively provide a single-letter characterization of the sparse PCA problem.

Sparse PCA via Covariance Thresholding

In sparse principal component analysis we are given noisy observations of a low-rank matrix of dimension $ntimes p$ and seek to reconstruct it under additional sparsity assumptions. In particular, we assume here each of the principal components $mathbf{v}_1,dots,mathbf{v}_r$ has at most $s_0$ non-zero entries. We are particularly interested in the high dimensional regime wherein $p$ is comparable to, or even much larger than $n$. In an influential paper, cite{johnstone2004sparse} introduced a simple algorithm that estimates the support of the principal vectors $mathbf{v}_1,dots,mathbf{v}_r$ by the largest entries in the diagonal of the empirical covariance. This method can be shown to identify the correct support with high probability if $s_0le K_1sqrt{n/log p}$, and to fail with high probability if $s_0ge K_2 sqrt{n/log p}$ for two constants $0<K_1,K_2<infty$. Despite a considerable amount of work over the last ten years, no practical algorithm exists with provably better support recovery guarantees. Here we analyze a covariance thresholding algorithm that was recently proposed by cite{KrauthgamerSPCA}. On the basis of numerical simulations (for the rank-one case), these authors conjectured that covariance thresholding correctly recover the support with high probability for $s_0le Ksqrt{n}$ (assuming $n$ of the same order as $p$). We prove this conjecture, and in fact establish a more general guarantee including higher-rank as well as $n$ much smaller than $p$. Recent lower bounds cite{berthet2013computational, ma2015sum} suggest that no polynomial time algorithm can do significantly better. The key technical component of our analysis develops new bounds on the norm of kernel random matrices, in regimes that were not considered before.

Finding Hidden Cliques of Size sqrt{N/e} in Nearly Linear Time

Consider an Erdos-Renyi random graph in which each edge is present independently with probability 1/2, except for a subset $sC_N$ 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 $|sC_N|ge 1.261sqrt{N}$ cite{dekel2011finding}. Spectral methods can be shown to fail on cliques smaller than $sqrt{N}$. In this paper we describe a nearly linear time algorithm that succeeds with high probability for $|sC_N|ge (1+eps)sqrt{N/e}$ for any $eps>0$. 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 $N$ vertices). For large girth regular graphs of degree $(Delta+1)$ we prove that `local algorithms succeed if $|sC_N|ge (1+eps)N/sqrt{eDelta}$ and fail if $|sC_N|le(1-eps)N/sqrt{eDelta}$.

Power Controlled Adaptive Sum-Capacity of Fading MACs with Distributed CSI

We consider the problem of finding optimal, fair and distributed power-rate strategies to achieve the sum capacity of the Gaussian multiple-access block-fading channel. In here, the transmitters have access to only their own fading coefficients, while the receiver has global access to all the fading coefficients. Outage is not permitted in any communication block. The resulting average sum-throughput is also known as `power-controlled adaptive sum-capacity, which appears as an open problem in literature. This paper presents the power-controlled adaptive sum-capacity of a wide-class of popular MAC models. In particular, we propose a power-rate strategy in the presence of distributed channel state information (CSI), which is throughput optimal when all the users have identical channel statistics. The proposed scheme also has an efficient implementation using successive cancellation and rate-splitting. We propose an upperbound when the channel laws are not identical. Furthermore, the optimal schemes are extended to situations in which each transmitter has additional finite-rate partial CSI on the link quality of others.