Search

In phase retrieval we want to recover an unknown signal $\boldsymbol x\in\mathbb C^d$ from $n$ quadratic measurements of the form $y_i = |\langle{\boldsymbol a}_i,{\boldsymbol x}\rangle|^2+w_i$ where $\boldsymbol a_i\in \mathbb C^d$ are known sensing vectors and $w_i$ is measurement noise. We ask the following weak recovery question: what is the minimum number of measurements $n$ needed to produce an estimator $\hat{\boldsymbol x}(\boldsymbol y)$ that is positively correlated with the signal $\boldsymbol x$? We consider the case of Gaussian vectors $\boldsymbol a_i$. We prove that - in the high-dimensional limit - a sharp phase transition takes place, and we locate the threshold in the regime of vanishingly small noise. For $n\le d-o(d)$ no estimator can do significantly better than random and achieve a strictly positive correlation. For $n\ge d+o(d)$ a simple spectral estimator achieves a positive correlation. Surprisingly, numerical simulations with the same spectral estimator demonstrate promising performance with realistic sensing matrices. Spectral methods are used to initialize non-convex optimization algorithms in phase retrieval, and our approach can boost the performance in this setting as well. Our impossibility result is based on classical information-theory arguments. The spectral algorithm computes the leading eigenvector of a weighted empirical covariance matrix. We obtain a sharp characterization of the spectral properties of this random matrix using tools from free probability and generalizing a recent result by Lu and Li. Both the upper and lower bound generalize beyond phase retrieval to measurements $y_i$ produced according to a generalized linear model. As a byproduct of our analysis, we compare the threshold of the proposed spectral method with that of a message passing algorithm., Comment: 63 pages, 3 figures, presented at COLT'18 and accepted at Foundations of Computational Mathematics

We give explicit parametrizations of the algebraic tori $$\mathbb {T}_{n}$$Tn over any finite field $$\mathbb {F}_{q}$$Fq for any prime power $$n$$n. Applying the construction for $$n=3$$n=3 to a quadratic field $$\mathbb {F}_{q^2}$$Fq2 we show that the set of $$\mathbb {F}_q$$Fq-rational points of the torus $$\mathbb {T}_{6}$$T6 is birationally equivalent to the affine part of a Singer arc in $$\mathbb {P}^2(\mathbb {F}_{q^2})$$P2(Fq2). This gives a simple, yet efficient compression and decompression algorithm from $$\mathbb {T}_{6}(\mathbb {F}_{q})$$T6(Fq) to $$\mathbb {A}^2(\mathbb {F}_{q})$$A2(Fq) that can be substituted in the faster implementation of CEILIDH (Granger et al., in Algorithmic number theory, pp 235---249, Springer, Berlin, 2004) achieving a theoretical 30 % speedup and that is also cheaper than the recently proposed factor-$$6$$6 compression technique in Karabina (IEEE Trans Inf Theory 58(5):3293---3304, 2012). The compression methods here presented have a wide class of applications to public-key and pairing-based cryptography over any finite field.

Consider an Erdos---Renyi random graph in which each edge is present independently with probability $$1/2$$1/2, except for a subset $$\mathsf{C}_N$$CN 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 algorithm of Dekel et al. (ANALCO. SIAM, pp 67---75, 2011) provably identifies the clique $$\mathsf{C}_N$$CN in linear time, provided $$|\mathsf{C}_N|\ge 1.261\sqrt{N}$$|CN|?1.261N. Spectral methods can be shown to fail on cliques smaller than $$\sqrt{N}$$N. In this paper we describe a nearly linear-time algorithm that succeeds with high probability for $$|\mathsf{C}_N|\ge (1+{\varepsilon })\sqrt{N/e}$$|CN|?(1+?)N/e for any $${\varepsilon }>0$$?>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$$N vertices). For large-girth regular graphs of degree $$(\varDelta +1)$$(Δ+1) we prove that so-called local algorithms succeed if $$|\mathsf{C}_N|\ge (1+{\varepsilon })N/\sqrt{e\varDelta }$$|CN|?(1+?)N/eΔ and fail if $$|\mathsf{C}_N|\le (1-{\varepsilon })N/\sqrt{e\varDelta }$$|CN|≤(1-?)N/eΔ.

We consider the Ising model with inverse temperature β and without external field on sequences of graphs Gn which converge locally to the k-regular tree. We show that for such graphs the Ising measure locally weakly converges to the symmetric mixture of the Ising model with + boundary conditions and the − boundary conditions on the k-regular tree with inverse temperature β. In the case where the graphs Gn are expanders we derive a more detailed understanding by showing convergence of the Ising measure conditional on positive magnetization (sum of spins) to the + measure on the tree.

Gallager codes are the best error-correcting codes to-date. In this paper we study them by using the tools of statistical mechanics. The corresponding statistical mechanics model is a spin model on a sparse random graph. The model can be solved by elementary methods (i.e. without replicas) in a large connectivity limit. For low enough temperatures it presents a completely frozen glassy phase (q_{EA}=1). The same scenario is shown to hold for finite connectivities. In this case we adopt the replica approach and exhibit a one-step replica symmetry breaking order parameter. We argue that our ansatz yields the exact solution of the model. This allows us to determine the whole phase diagram and to understand the performances of Gallager codes., Comment: 27 pages, 8 eps figures