2 April 2018 in Communications on Pure and Applied Mathematics
20 October 2009 in Discrete & Computational Geometry
Geographic Routing is a family of routing algorithms that uses geographic point locations as addresses for the purposes of routing. Such routing algorithms have proven to be both simple to implement and heuristically effective when applied to wireless sensor networks. Greedy Routing is a natural abstraction of this model in which nodes are assigned virtual coordinates in a metric space, and these coordinates are used to perform point-to-point routing. Here we resolve a conjecture of Papadimitriou and Ratajczak that every 3-connected planar graph admits a greedy embedding into the Euclidean plane. This immediately implies that all 3-connected graphs that exclude K 3,3 as a minor admit a greedy embedding into the Euclidean plane. We also prove a combinatorial condition that guarantees nonembeddability. We use this result to construct graphs that can be greedily embedded into the Euclidean plane, but for which no spanning tree admits such an embedding.
4 March 2015 in Algorithmica
We present a new algorithm for independent component analysis which has provable performance guarantees. In particular, suppose we are given samples of the form \(y = Ax + \eta \) where \(A\) is an unknown but non-singular \(n \times n\) matrix, \(x\) is a random variable whose coordinates are independent and have a fourth order moment strictly less than that of a standard Gaussian random variable and \(\eta \) is an \(n\) -dimensional Gaussian random variable with unknown covariance \(\varSigma \) : We give an algorithm that provably recovers \(A\) and \(\varSigma \) up to an additive \(\epsilon \) and whose running time and sample complexity are polynomial in \(n\) and \(1 / \epsilon \) . To accomplish this, we introduce a novel “quasi-whitening” step that may be useful in other applications where there is additive Gaussian noise whose covariance is unknown. We also give a general framework for finding all local optima of a function (given an oracle for approximately finding just one) and this is a crucial step in our algorithm, one that has been overlooked in previous attempts, and allows us to control the accumulation of error when we find the columns of \(A\) one by one via local search.
29 March 2022 in Mathematical Programming
In the noisy tensor completion problem we observementries (whose location is chosen uniformly at random) from an unknown $$n_1 \times n_2 \times n_3$$ tensorT. We assume thatTis entry-wise close to being rankr. Our goal is to fill in its missing entries using as few observations as possible. Let $$n = \max (n_1, n_2, n_3)$$ . We show that if $$m > rsim n^{3/2} r$$ then there is a polynomial time algorithm based on the sixth level of the sum-of-squares hierarchy for completing it. Our estimate agrees with almost all ofT’s entries almost exactly and works even when our observations are corrupted by noise. This is also the first algorithm for tensor completion that works in the overcomplete case when $$r > n$$ , and in fact it works all the way up to $$r = n^{3/2-\epsilon }$$ . Our proofs are short and simple and are based on establishing a new connection between noisy tensor completion (through the language of Rademacher complexity) and the task of refuting random constraint satisfaction problems. This connection seems to have gone unnoticed even in the context of matrix completion. Furthermore, we use this connection to show matching lower bounds. Our main technical result is in characterizing the Rademacher complexity of the sequence of norms that arise in the sum-of-squares relaxations to the tensor nuclear norm. These results point to an interesting new direction: Can we explore computational vs. sample complexity tradeoffs through the sum-of-squares hierarchy?
23 May 2023 in Journal of the ACM
This work represents a natural coalescence of two important lines of work — learning mixtures of Gaussians and algorithmic robust statistics. In particular, we give the first provably robust algorithm for learning mixtures of any constant number of Gaussians. We require only mild assumptions on the mixing weights and that the total variation distance between components is bounded away from zero. At the heart of our algorithm is a new method for proving a type of dimension-independent polynomial identifiability — which we call robust identifiability — through applying a carefully chosen sequence of differential operations to certain generating functions that not only encode the parameters we would like to learn but also the system of polynomial equations we would like to solve. We show how the symbolic identities we derive can be directly used to analyze a natural sum-of-squares relaxation.