User roberto imbuzeiro oliveira - MathOverflow

Recovering a linear map from a non-linear approximation

2011-05-26T03:07:48Z

The problem described here is algorithmic. We are given "black box access" to a map $f:R^d\to R^d$. By this we mean that one may query the value of $f(v)$ for an arbitrary $v\in R^d$.

We assume that there is a symmetric $d\times d$ matrix $T$ with spectral norm $\|T\|_{\rm sp}\leq 1$ such that: $$\forall v\in R^d : |Tv - f(v)|\leq \epsilon|v|,$$ where $|\cdot|$ denotes the Euclidean norm.

Problem: Given $k\in N$, find a $C=C(d,k,\epsilon)$ that is as small as possible such that the following holds. There exists an efficient algorithm that queries the values of $f(v)$ for at most $k$ different vectors and outputs a symmetric matrix $S$ with $$\|S-T\|_{sp}\leq C\epsilon.$$

Ideally, I would like $C>0$ to be independent of $d$.

Inneficient solution with $k\gg 2^d$ and $C\approx 1$: Let ${SYM}_d $ be the vector space consisting of all $d\times d$ symmetric matrices. Notice that:

$$T \in \bigcap_{w,v\in S^{d-1}}(S\in SYM_d : {\langle w,Tv\rangle\in [\langle w,f(v)\rangle-\epsilon,\langle w,f(v)\rangle+\epsilon]})$$ where $S^{d-1}$ is the ($d-1$)-dimensional sphere and $\langle \cdot,\cdot\cdot\rangle$ is the standard inner product. By replacing the sphere with a fine enough finite mesh, one may approximate the above intersection by a polytope in $SYM_d$ with diameter $\leq 2 \epsilon$ where $T$ lies. Any matrix $S$ in that polytope satisfies $\|T-S\|_{\rm sp}\leq 2\epsilon$.

Efficient solution with $C=d$. Compute $f(e_i)$ for each vector in the canonical basis. ~~Let $S$ map $e_i$ to $f(e_i)$.~~ Let $S_0$ map $e_i$ to $f(e_i)$; this is $d\epsilon$-close to $T$. Now take $S = (S_0 + S_0^*)/2$.

Can one do better? I am guessing this might be a known problem, but I could not find any references.

Wasserstein distance in R^d from one dimensional marginals

2010-09-04T00:46:43Z

This question occurred to me while I was reading Klartag's papers on central limit theorems for convex bodies.

Given probability measures $\mu$, $\nu$ on (the Borel $\sigma$-field of) $R^d$ with finite first moments, their Wasserstein distance is given by: $$W_{R^d}(\mu,\nu) = \sup \mbox{ of }\int_{R^d}f d\mu-\int_{R^d}f d\nu\mbox{ over all 1-Lipschitz }f:R^d\to R.$$

(NB: there was an error in this formula -- an inf in the place of the sup.)

Given a vector $v\in R^d$, let $\mu_v$ be the distribution of $X.v$, where $X$ has distribution $\mu$. Define $\nu_v$ analogously. Note that $\mu_v$ and $\nu_v$ are distributions over $R$.

Question: is there a constant $C_d>0$ depending on $d$ only such that: $$W_{R^d}(\mu,\nu)\leq C_d\sup_{v\in R^d, |v|=1}W_{R}(\mu_v,\nu_v)?$$ If so, how does $C_d$ grow with $d$?

An illustrative example: Assume $Z$ is uniform over a $D-1$ dimensional sphere $S^{D-1}$ in $R^D$. Any one-dimensional marginal of $\sqrt{D-1}Z$ is approximatelly Gaussian. Now let $\mu$ be the law of the first $d$ coordinates of $\sqrt{D-1}Z$, and $\nu$ be the standard Gaussian distribution on $R^d$. Can one deduce from the previous statement alone that $\mu$ and $\nu$ are close?

Another example: Let $Z$ be a random vector in $R^D$ with mean $0$ and covariance matrix $I_D$, $D\gg 1$. Old results of Sudakov (quoted here) show that "most" one-dimensional marginals of $Z$ are close to $|Z|N$ where $N$ is standard normal and independent from $Z$. A positive answer to the above question would lead to typical results for $d$-dimensional projections of $Z$.

Coalescing random walks: a bound for the full coalescence time?

2010-09-01T00:24:42Z

Start a random walk from each vertex of a graph $G$. Let the walkers evolve independently, except that when two of the walkers meet (ie. occupy the same vertex at the same time), they coalesce into one single walker. (Alternatively, one may label the walkers with numbers $1,\dots,n$ and say that walker $i$ is killed at the first time it meets a walker with smaller index.)

It is not hard to show that, if $G$ is connected and finite, there will be a first time $C$ when all walks will have coalesced into one ($C$ is the first time when only one alive particle remains in the "killing description"). The following is Open Problem $13$ in Chapter $14$ of Aldous and Fill's manuscript: http://www.stat.berkeley.edu/~aldous/RWG/book.html.

Problem: Prove that there exists a universal constant such that: $$E(C)\leq K\max_{v,w\in V(G)}E_v(H_w)$$ where $V(G)$ is the vertex set of $G$ and $H_w$ is the hitting time of vertex $w$.

My question is: does anyone know of any work on this problem? I know there is a paper by Cox which studies the distributional limit of $C$ over $Z_n^d$ for $n\gg 1$ and $d$ fixed; a solution for the Problem follows from this in this specific family of graphs. What else is out there? Has the problem actually been solved by someone?

Answer by Roberto Imbuzeiro Oliveira for Coalescing random walks: a bound for the full coalescence time?

2010-09-04T03:32:37Z

fedja was right to guess that I had an idea to solve the problem. Reading that Yuval Peres is working on it scared me into writing something down as quickly as possible. Any comments on my manuscript (below) are very welcome.

http://arxiv.org/abs/1009.0664

Answer by Roberto Imbuzeiro Oliveira for Looking for an explicit formula for a limit of a binomial-like expression

2010-09-04T00:22:25Z

Here's a probabilistic solution to your problem. Suppose $X_N$ is a binomial random variable with parameters $N$ and $s/N$ (ie. $X_N$ counts the number of heads in $N$ independent coin flips, each with probability $s/N$ of heads). Also let $P$ be a Poisson random variable with mean $s$, so that for all non-negative integers $k$: $$Prob[P=k] = e^{-s}\frac{s^k}{k!}.$$ A well-known result sometimes called the law of rare events implies that the distribution of $X_N$ converges to that of $P$ as $N\to +\infty$. In particular, for any bounded real-valued function $f$ defined on the non-negative integers: $$E(f(X_N)) = \sum_{k=0}^N \binom{N}{k}\left(1-\frac{s}{N}\right)^{N-k}\left(\frac{s}{N}\right)^{k}f(k)\to E(f(P))=\sum_{k=0}^{+\infty}e^{-s}\frac{s^k}{k!}f(k).$$

Apply this to $f$ satisfying $f(x)=1/x$ if $x>0$, $f(0)=0$, and the LHS becomes your expression. The RHS becomes: $$\sum_{k=1}^{+\infty}e^{-s}\frac{s^k}{k!\times k} = e^{-s}\int_{0}^{s}\frac{e^{u}-1}{u}du,$$ which I guess is the same as the previous answer.

Added note: a quantitative version of the law of rare events gives the error bound: $$\forall f:N\to [0,1], |E(f(X_N))-E(f(P))|\leq s\left(1-e^{-s/N}\right);$$ this allows for simultaneous limits in N and $s$, and goes to $0$ iff $s^2/N\to 0$.

Answer by Roberto Imbuzeiro Oliveira for Undergraduate Probability Topics

2010-09-02T15:08:44Z

Here is another suggestion involving Markov chains: Example 1 in Diaconis' The Markov Chain Monte Carlo revolution. This is a very surprising application of MCMC to decoding messages exchanged between interns in California's prision system.

Answer by Roberto Imbuzeiro Oliveira for Random geometric graphs and spanners

2010-09-01T16:21:10Z

I assume you meant $p=(1+\varepsilon)p_1$ in the first question, in which case the answer seems to be "no".

To see this, we note that, with high probability:

(i) The size of $C$ is $\Theta(n)$ (this is the classical result);

(ii) The average graph-theoretic distance $d_G(x,y)$ between two randomly chosen vertices $x,y\in C$ is concentrated around $c\ln n$ for some $c>0$ (this is proven in eg. Durrett's Random Graph Dynamics);

(iii) All points $p$ in the square are such that the ball of radius $r$ around $p$ contains $\Theta(r^2 n)$ points of $C$, simultaneously for all $r\gg \ln^2n/n$. (To see this, notice that the positions of points in the square are independent from their being or not in the giant component, then apply a VC dimension argument + part (i)).

Now let $\varepsilon>0$ be small (and fixed) and let $n$ grow. By item (ii), there is a high probability that one can find a point $p\in C$ such that the set $$P(p)\equiv {\mbox{all points $q$ in $C$ with }\frac{d_G(p,q)}{c\ln n}\in [1/2,1]}$$ has size $\geq (1-\varepsilon^2)|C|$. By part (iii), there is a high probability that at least one point $q_0\in P(p)$ with $|p-q_0|\leq \varepsilon$ and at least one point $q_1\in P(p)$ with $q_1\geq 1/3$. Since $d_G(p,q_0),d_G(p,q_1)=O(\ln n)$, this shows that: $$\frac{d_G(p,q_0)}{|p-q_0|}\geq \Omega\left(\frac{1}{\varepsilon}\right)\frac{d_G(p,q_1)}{|p-q_1|}.$$

Comment by Roberto Imbuzeiro Oliveira

2011-05-26T14:18:19Z

I am assuming that f is close to a linear map, which rules out elementwise exponentiation. Presumably the derivative of f at any point is close to T, but (i) I am not assuming that f is differentiable, and (ii) even if it is, it is not entirely clear how this could be useful in my black box model. –

Comment by Roberto Imbuzeiro Oliveira

2010-10-01T10:04:09Z

Thanks! I guess I had the dual definition in mind when writing this.

Comment by Roberto Imbuzeiro Oliveira

2010-09-22T11:52:10Z

A continuous-time Markov chain over a finite set $S$ is a process such that, for all distinct $x,y\in S$, the chance of being at $y$ at time $t+\epsilon$, given that the state at time $t$ is $x$, $q(x,y)\epsilon + o(\epsilon)$, where $q(x,y)$ are the so-called transition rates. This moves by "jumps" only.

Comment by Roberto Imbuzeiro Oliveira

2010-09-01T15:48:57Z

Thanks for the feedback. Do you have any references on the self-intersection question?