User roberto imbuzeiro oliveira - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T09:39:42Z http://mathoverflow.net/feeds/user/8354 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66014/recovering-a-linear-map-from-a-non-linear-approximation Recovering a linear map from a non-linear approximation Roberto Imbuzeiro Oliveira 2011-05-26T03:07:48Z 2011-05-26T18:27:39Z <p>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$. </p> <p>We <i>assume</i> 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.</p> <p><b>Problem:</b> 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.$$ </p> <p>Ideally, I would like $C>0$ to be independent of $d$. </p> <p><b>Inneficient solution with $k\gg 2^d$ and $C\approx 1$:</b> Let ${SYM}_d$ be the vector space consisting of all $d\times d$ symmetric matrices. Notice that: </p> <p>$$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$. </p> <p><b>Efficient solution with $C=d$.</b> Compute $f(e_i)$ for each vector in the canonical basis. <s>Let $S$ map $e_i$ to $f(e_i)$.</s> 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$.</p> <p>Can one do better? I am guessing this might be a known problem, but I could not find any references. </p> http://mathoverflow.net/questions/37677/wasserstein-distance-in-rd-from-one-dimensional-marginals Wasserstein distance in R^d from one dimensional marginals Roberto Imbuzeiro Oliveira 2010-09-04T00:46:43Z 2010-10-02T10:30:41Z <p>This question occurred to me while I was reading <a href="http://www.math.tau.ac.il/~klartagb/publications.html" rel="nofollow">Klartag's papers on central limit theorems for convex bodies</a>. </p> <p>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.$$</p> <p>(<b>NB</b>: there was an error in this formula -- an inf in the place of the sup.)</p> <p>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$.</p> <p><b>Question:</b> 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$?</p> <p><b>An illustrative example:</b> 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?</p> <p><b>Another example:</b> 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 <a href="http://www.springerlink.com/content/33ype6awh6lqb50d/" rel="nofollow">here</a>) 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$. </p> http://mathoverflow.net/questions/37337/coalescing-random-walks-a-bound-for-the-full-coalescence-time Coalescing random walks: a bound for the full coalescence time? Roberto Imbuzeiro Oliveira 2010-09-01T00:24:42Z 2010-09-22T02:45:56Z <p>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.) </p> <p>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: <a href="http://www.stat.berkeley.edu/~aldous/RWG/book.html" rel="nofollow">http://www.stat.berkeley.edu/~aldous/RWG/book.html.</a></p> <p><b>Problem:</b> 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$.</p> <p>My <b>question</b> 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? </p> http://mathoverflow.net/questions/37337/coalescing-random-walks-a-bound-for-the-full-coalescence-time/37685#37685 Answer by Roberto Imbuzeiro Oliveira for Coalescing random walks: a bound for the full coalescence time? Roberto Imbuzeiro Oliveira 2010-09-04T03:32:37Z 2010-09-22T02:45:56Z <p>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.</p> <p><a href="http://arxiv.org/abs/1009.0664" rel="nofollow">http://arxiv.org/abs/1009.0664</a></p> http://mathoverflow.net/questions/37248/looking-for-an-explicit-formula-for-a-limit-of-a-binomial-like-expression/37676#37676 Answer by Roberto Imbuzeiro Oliveira for Looking for an explicit formula for a limit of a binomial-like expression Roberto Imbuzeiro Oliveira 2010-09-04T00:22:25Z 2010-09-04T00:54:15Z <p>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 <a href="http://en.wikipedia.org/wiki/Poisson_distribution#How_does_this_distribution_arise.3F_.E2.80.94_The_law_of_rare_events" rel="nofollow">the law of rare events</a> 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).$$</p> <p>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.</p> <p><b>Added note:</b> 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$.</p> http://mathoverflow.net/questions/37408/undergraduate-probability-topics/37507#37507 Answer by Roberto Imbuzeiro Oliveira for Undergraduate Probability Topics Roberto Imbuzeiro Oliveira 2010-09-02T15:08:44Z 2010-09-02T15:08:44Z <p>Here is another suggestion involving Markov chains: Example 1 in Diaconis' <a href="http://www.ams.org/journals/bull/2009-46-02/S0273-0979-08-01238-X/home.html" rel="nofollow">The Markov Chain Monte Carlo revolution</a>. This is a very surprising application of MCMC to decoding messages exchanged between interns in California's prision system. </p> http://mathoverflow.net/questions/28444/random-geometric-graphs-and-spanners/37397#37397 Answer by Roberto Imbuzeiro Oliveira for Random geometric graphs and spanners Roberto Imbuzeiro Oliveira 2010-09-01T16:21:10Z 2010-09-01T16:21:10Z <p>I assume you meant $p=(1+\varepsilon)p_1$ in the first question, in which case the answer seems to be "no".</p> <p>To see this, we note that, with high probability:</p> <p>(i) The size of $C$ is $\Theta(n)$ (this is the classical result);<br></p> <p>(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 <i>Random Graph Dynamics</i>);<br></p> <p>(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)).</p> <p>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|}.$$</p> http://mathoverflow.net/questions/66014/recovering-a-linear-map-from-a-non-linear-approximation Comment by Roberto Imbuzeiro Oliveira Roberto Imbuzeiro Oliveira 2011-05-26T14:18:19Z 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. – http://mathoverflow.net/questions/37677/wasserstein-distance-in-rd-from-one-dimensional-marginals Comment by Roberto Imbuzeiro Oliveira Roberto Imbuzeiro Oliveira 2010-10-01T10:04:09Z 2010-10-01T10:04:09Z Thanks! I guess I had the dual definition in mind when writing this. http://mathoverflow.net/questions/37337/coalescing-random-walks-a-bound-for-the-full-coalescence-time/37685#37685 Comment by Roberto Imbuzeiro Oliveira Roberto Imbuzeiro Oliveira 2010-09-22T11:52:10Z 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 &quot;jumps&quot; only. http://mathoverflow.net/questions/37337/coalescing-random-walks-a-bound-for-the-full-coalescence-time Comment by Roberto Imbuzeiro Oliveira Roberto Imbuzeiro Oliveira 2010-09-01T15:48:57Z 2010-09-01T15:48:57Z Thanks for the feedback. Do you have any references on the self-intersection question?