Van H. Vu

SODA Conference 2024 Conference Paper

Matrix Perturbation: Davis-Kahan in the Infinity Norm

• Abhinav Bhardwaj
• Van H. Vu

FOCS Conference 2015 Conference Paper

Random Matrices: l1 Concentration and Dictionary Learning with Few Samples

• Kyle Luh
• Van H. Vu

Let X be a sparse random matrix of size n by p (p >> n). We prove that if p > C n log4 n, then with probability 1-o(1), |XT v|1 is close to its expectation for all vectors v in Rn (simultaneously). The bound on p is sharp up to the polylogarithmic factor. The study of this problem is directly motivated by an application. Let A be an n by n matrix, X be an n by p matrix and Y = AX. A challenging and important problem in data analysis, motivated by dictionary learning and other practical problems, is to recover both A and X, given Y. Under normal circumstances, it is clear that this problem is underdetermined. However, in the case when X is sparse and random, Spiel man, Wang and Wright showed that one can recover both A and X efficiently from Y with high probability, given that p (the number of samples) is sufficiently large. Their method works for p > C n2 log2 n and they conjectured that p > C n log n suffices. The bound n log n is sharp for an obvious information theoretical reason. The matrix concentration result verifies the Spiel man et. Al. Conjecture up to a log3 n factor. Our proof of the concentration result is based on two ideas. The first is an economical way to apply the union bound. The second is a refined version of Bernstein's concentration inequality for a sum of independent variables. Both have nothing to do with random matrices and are applicable in general settings.

STOC Conference 2007 Conference Paper

The condition number of a randomly perturbed matrix

• Van H. Vu
• Terence Tao

Let M be an arbitrary n by n matrix. We study the conditionnumber a random perturbation M+N n of M, where N n is arandom matrix. It is shown that, under very general conditions on M and M n , the condition number of M+N n is polynomial in n with very high probability. The main novelty here is that we allow N n to have discrete distribution.

STOC Conference 2005 Conference Paper

On random pm 1 matrices: singularity and determinant

• Terence Tao
• Van H. Vu

We proved several results concerning the determinant of a random pm 1 matrix. In particular, we show that with high probability, the determinant has absolute value very close to √n!.

STOC Conference 2005 Conference Paper

Spectral norm of random matrices

• Van H. Vu

In this paper, we present a new upper bound for the spectral norm of symmetric random matrices with independent (but not necessarily identical) entries. Our results improve an earlier result of Füredi and Komlós and also correct an incomplete argument in their proof.

STOC Conference 2003 Conference Paper

Generating random regular graphs

• Jeong Han Kim
• Van H. Vu

Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [9] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d=O(n 1/3-ε ) , it is shown that the algorithm generates an asymptotically uniform random d -regular graph on n vertices in time O(nd 2 ) . This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author.Besides being perhaps the only algorithm which works for relatively large d in practical time, our result also has a significant theoretical value, as it can be used to derive many properties of uniform random regular graphs.

SODA Conference 2003 Conference Paper

Multirate rearrangeable clos networks and a generalized edge coloring problem on bipartite graphs

• Hung Q. Ngo 0001
• Van H. Vu

FOCS Conference 2000 Conference Paper

The Cover Time, the Blanket Time, and the Matthews Bound

• Jeff Kahn 0001
• Jeong Han Kim
• László Lovász 0001
• Van H. Vu

We prove upper and lower bounds and give an approximation algorithm for the cover time of the random walk on a graph. We introduce a parameter M motivated by the well-known Matthews bounds (P. Matthews, 1988) on the cover time, C, and prove that M/2<C= O(M(lnlnn)/sup 2/). We give a deterministic-polynomial time algorithm to approximate M within a factor of 2; this then approximates C within a factor of O((lnlnn)/sup 2/), improving the previous bound O(lnn) due to Matthews. The blanket time B was introduced by P. Winkler and D. Zuckerman (1996): it is the expectation of the first time when all vertices are visited within a constant factor of the number of times suggested by the stationary distribution. Obviously C/spl les/B. Winkler and Zuckerman conjectured B=O(C) and proved B=O(Clnn). Our bounds above are also valid for the blanket time, and so it follows that B=O(C(lnlnn)/sup 2/).

FOCS Conference 1999 Conference Paper

Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics

• Christian Borgs
• Jennifer T. Chayes
• Alan M. Frieze
• Jeong Han Kim
• Prasad Tetali
• Eric Vigoda
• Van H. Vu

Studies two widely used algorithms, Glauber dynamics and the Swendsen-Wang (1987) algorithm, on rectangular subsets of the hypercubic lattice Z/sup d/. We prove that, under certain circumstances, the mixing time in a box of side length L with periodic boundary conditions can be exponential in L/sup d-1/. In other words, under these circumstances, the mixing in these widely used algorithms is not rapid; instead it is torpid. The models we study are the independent set model and the q-state Potts model. For both models, we prove that Glauber dynamics is torpid in the region with phase coexistence. For the Potts model, we prove that the Swendsen-Wang mixing is torpid at the phase transition point.

NeurIPS Conference 1997 Conference Paper

On the Infeasibility of Training Neural Networks with Small Squared Errors

• Van H. Vu

We demonstrate that the problem of training neural networks with small (average) squared error is computationally intractable. Con(cid: 173) sider a data set of M points (Xi, Yi), i = 1, 2, .. ., M, where Xi are input vectors from Rd, Yi are real outputs (Yi E R). For a net- work 10 in some class F of neural networks, (11M) L~l (fO(Xi)(cid: 173) Yi)2)1/2 - inlfEF(l/ M) "2: f! 1 (f(Xi) - YJ2)1/2 is the (avarage) rel(cid: 173) ative error occurs when one tries to fit the data set by 10. We will prove for several classes F of neural networks that achieving a rela(cid: 173) tive error smaller than some fixed positive threshold (independent from the size of the data set) is NP-hard.

FOCS Conference 1996 Conference Paper

The Geometry of Coin-Weighing Problems

• Noga Alon
• Dmitry N. Kozlov
• Van H. Vu

Given a set of m coins out of a collection of coins of k unknown distinct weights, the authors wish to decide if all the m given coins have the same weight or not using the minimum possible number of weighings in a regular balance beam. Let m(n, k) denote the maximum possible number of coins for which the above problem can be solved in n weighings. They show that m(n, 2)=n/sup ( 1/2 +o(1))n/, whereas for all 3/spl les/k/spl les/n+1, m(n, k) is much smaller than m(n, 2) and satisfies m(n, k)=/spl Theta/(n log n/log k). The proofs have an interesting geometric flavour; and combine linear algebra techniques with geometric probabilistic and combinatorial arguments.