most recent 30 from http://mathoverflow.net 2013-06-18T07:06:21Z http://mathoverflow.net/feeds/user/13049 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/132520/spectral-theory-based-on-projections-onto-convex-sets passerby51 2013-06-01T16:43:53Z 2013-06-01T16:43:53Z

<p>Consider finite-dimensional settings. Usual spectral theory decomposes a self-adjoint operators $A$ as a linear combination of orthogonal projections <code>$\{P_i\}$</code> onto linear subspaces, e.g. <code>$A = \sum_{i=1}^r \lambda_i P_i$</code>. </p> <p>Has there been any attempt to relax the linearity of the subspaces. For example, are there results where one tries to represent $A$ as the sum of projections onto convex sets (say convex cones)?</p> <p>Here is a vaguely related (open-ended) problem: a version of nonnegative matrix factorization of $A$ attempts to write $A = \sum_{i=1}^r \lambda_i u_i u_i^T$ where $u_i \in \mathbb{R}_+$ are vectors with nonnegative coordinates (maybe with some additional constraints). Can this be related to the above problem in any way?</p>

http://mathoverflow.net/questions/125509/gaussian-width-or-metric-entropy-for-the-intersection-of-the-ell-1-and-ell passerby51 2013-03-25T04:34:08Z 2013-03-25T16:14:10Z

<p>Let <code>$B_p := \{ x \in \mathbb{R}^d:\; \|x\|_p \le 1\}$</code> where <code>$\|x\|_p := (\sum_{i=1}^d |x_i|^p)^{1/p}$</code> is the <code>$\ell_p$</code> norm.</p> <p>(1) Let $t \in (0,1)$. Can we give an estimate on $$\mathbb{E} \Big[\sup_{\|x\|_1 \le \frac{1}{1-t}, \; \|x\|_2 \le \frac1{t} } \langle x,w\rangle \Big]$$ where $w$ has standard $d$-dimensional Gaussian distribution? More specifically, can we choose $t = t_n$ such that this scales faster, as $n \to \infty$, than either of the cases $t = 0$ or $t=1$?</p> <p>Original question: What is the metric entropy of <code>$B_1 \cap (t B_2)$</code> (in $\ell_2$ norm) for values of $t$ for which the intersection is nontrivial? In particular, how does it depend on $t$?</p>

http://mathoverflow.net/questions/121546/2-wasserstein-optimal-transport-and-extension-to-the-set-of-all-signed-measures passerby51 2013-02-12T02:14:20Z 2013-02-12T02:14:20Z

<p>Consider the 2-Wasserstein distance between probability measures $\mu$ and $\nu$ (on $\mathbb{R}^d$), defined as $$ d_{W_2}(\mu,\nu) = \inf_{\gamma} \int \|x-y\|^2 d\gamma(x,y) $$ where the $\inf$ is over all couplings $\gamma$ of $\mu$ and $\nu$. Can we define a norm (or something norm-like) on the space of signed measures (or a linear subspace of it containing the cone of probability measures) which gives rise to $W_2$ for probability measures. (I suppose not, but why?)</p> <p>If not, can we approximate $d_{W_2}$ by a norm?</p>

http://mathoverflow.net/questions/100266/a-covering-problem-for-the-hamming-cube passerby51 2012-06-21T18:32:45Z 2012-06-21T20:17:16Z

<p>Consider the set of all $k$-subsets of $\{1,\dots,n\}$, naturally identified with a subset $A$ of $\{0,1\}^n$ where each element has exactly $k$ ones. Is there a sharp bound known for $\epsilon$-covering of this set in the Hamming distance?</p> <p>More specifically, suppose that $k = \gamma n$ where $\gamma \in(0,1/2)$ is fixed. The cardinality of $A$ is asymptotically $|A| \sim e^{n h(\gamma)}$ where $h(\cdot)$ is the binary entropy function. Is there an $\epsilon$-covering of $A$ in Hamming distance with $e^{ \frac{C n}{\log n}}$ elements and say $\epsilon \le \frac{n}{(\log n)^{2}}$? In other words, how large $\epsilon$ needs to be to be able to go from cardinality being exponential in $n$ to it being exponential in $n / \log n$.</p>

http://mathoverflow.net/questions/96817/an-optimization-involving-random-graphs passerby51 2012-05-13T04:57:44Z 2012-05-14T06:03:53Z

<p>Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $-1$. Call this a configuration $\sigma \in \{+1,-1\}^n$. The number of $+1$s that we have to assign is exactly $s$ (hence the number of $-1$s is $n-s$.) Given a configuration $\sigma$, we look at each node $i$ and sum the values assigned to its neighbors, call this $\xi_i(\sigma)$. We then count the number of nodes for which $\xi_i(\sigma)$ is nonnegative:</p> <p>$$ N(\sigma) := \sum_{i=1}^n 1( \xi_i(\sigma) \ge 0). $$</p> <p>The question is: what is the configuration $\sigma$ that maximizes $N(\sigma)$? Can we give a bound on $(\max N)/n$ in terms of $s/n$. If it helps, the graph can be assumed to be Erdős-Renyi. </p>

http://mathoverflow.net/questions/55784/what-can-be-said-about-the-choice-of-a-prior-in-bayesian-statistics/55785#55785 passerby51 2011-02-17T21:04:30Z 2011-02-17T21:04:30Z

<p>Short answer from someone who doesn't know much about Bayesian statistics:</p> <p>You should read about "reference priors". Have a look here: <a href="http://arxiv.org/pdf/0904.0156" rel="nofollow">http://arxiv.org/pdf/0904.0156</a></p>

http://mathoverflow.net/questions/55783/elementary-question-in-differential-geometry passerby51 2011-02-17T20:56:16Z 2011-02-17T20:56:16Z

<p>I am trying to learn differential geometry (i.e., teach myself!) So here is a question that came up.</p> <p>For some $h > 0$, consider the cone </p> <p>$C_h = \{ (x,y,z) \; : \; 0 \le z = \sqrt{x^2 + y^2} &lt; h \} \subset \mathbb{R}^3$</p> <p>endowed with subspace topology. It seems that we can cover this with a single chart $(U,\phi)$ where $U = C_h$ and $\phi$ is the projection $\phi(x,y,z) = (x,y)$. So it seems that this defines a differentiable structure and we get a smooth ($C^\infty$) 2-dimensional manifold. (Is it correct?)</p> <p>Now consider the inclusion map $i : C_h \to \mathbb{R}^3$, is this maps smooth? It doesn't seem to me that it is. The expression of $i$ in the chart above is not smooth at $(0,0)$ and I don't seem to be able to find any other compatible chart around zero which has a smooth representation. (Haven't given it much thought though). If this is true how one shows that this map is not smooth. (Also, if this is true, a vague question is whether removing the origin is the only way to fix this problem)</p>

http://mathoverflow.net/questions/125509/gaussian-width-or-metric-entropy-for-the-intersection-of-the-ell-1-and-ell passerby51 2013-03-25T12:04:01Z 2013-03-25T12:04:01Z

Thanks. You are right. I forgot to mention the distance, and I am interested in the dependence on $t$ too.

http://mathoverflow.net/questions/121546/2-wasserstein-optimal-transport-and-extension-to-the-set-of-all-signed-measures passerby51 2013-02-12T16:37:13Z 2013-02-12T16:37:13Z

@Dirk: Thanks for the link.

http://mathoverflow.net/questions/121546/2-wasserstein-optimal-transport-and-extension-to-the-set-of-all-signed-measures passerby51 2013-02-12T04:21:02Z 2013-02-12T04:21:02Z

Thanks for the reference. I will think more about the dual version. A more direct approach is also welcome.

http://mathoverflow.net/questions/100266/a-covering-problem-for-the-hamming-cube/100284#100284 passerby51 2012-06-21T23:09:04Z 2012-06-21T23:09:04Z

... what I mean is I always seem to get the denominator to grow at most polynomially in $n$, hence the total number to be $e^{c n (1 - o(1)}$. Any tricks to get a $\log n$ drop in the exponent is appreciated.

http://mathoverflow.net/questions/100266/a-covering-problem-for-the-hamming-cube/100284#100284 passerby51 2012-06-21T23:02:54Z 2012-06-21T23:02:54Z

@Ryan, thanks for your response. I agree that a volume argument is pretty tight. I had tried it and I guess you end up with a bound of the form $\binom{n}{k} / [ \sum_{i=0}^r \binom{k}{i} \binom{n-k}{i} ]$ on the number of points required for an $r$-covering. I am having some difficulty, evaluating this asymptotically. Some rather rough calculations seems to suggest that you cannot get reduce the number from being exponential in $n$ (say $e^{cn(1+o(1)}$) if you require $ k = \gamma n$ and do want $r$ to grow sublienar in $n$.

http://mathoverflow.net/questions/96940/rank-k-of-a-sequence-of-random-variables passerby51 2012-05-14T20:02:26Z 2012-05-14T20:02:26Z

There is a great deal known about the ranks when $\{X_i\}$ is an i.i.d. sample. You can find some information in Chapter 13 of van der Vaart's Asymptotic Statistics: <a href="http://books.google.com/books?id=UEuQEM5RjWgC&amp;lpg=PR1&amp;pg=PA173#v=onepage&amp;q&amp;f=false" rel="nofollow">books.google.com/&hellip;</a>

http://mathoverflow.net/questions/96817/an-optimization-involving-random-graphs/96836#96836 passerby51 2012-05-14T15:15:00Z 2012-05-14T15:15:00Z

... I mean the R(n) in my original comment is the number of elements in each ball. It seems that one should take the radius to be 1. I am not even sure if taking a ball is a good idea. One might try other neighborhoods (of different shapes) of some size R(n), as your comment suggests that there might not much flexibility working with balls.

http://mathoverflow.net/questions/96817/an-optimization-involving-random-graphs/96836#96836 passerby51 2012-05-14T15:04:14Z 2012-05-14T15:04:14Z

Sorry, that was a typo, it was thinking of the number of elements in the ball to be ~ log n, not the radius.

http://mathoverflow.net/questions/96817/an-optimization-involving-random-graphs/96836#96836 passerby51 2012-05-14T14:21:16Z 2012-05-14T14:21:16Z

... otherwise maximality is violated. Then, one perhaps gets the estimate R(n) |S| \le n(1+o(1)). Another approach is to try to bound the expectation of N(\sigma) using a covering/chaining type argument. Say, one looks at the distance between two neighboring configurations $\sigma$ and $\sigma'$, defined by $d(\sigma,\sigma') := E |N(\sigma) - N(\sigma')|$ and then tries to cover the space of configurations in balls of some radius in this distance.

http://mathoverflow.net/questions/96817/an-optimization-involving-random-graphs/96836#96836 passerby51 2012-05-14T14:14:36Z 2012-05-14T14:14:36Z

Thanks. You estimate seems about right to me, The difficulty however is in proving an upper bound on $\max N$. I have a few ideas, none which developed much due to my lack of knowledge about random graphs. Using your terminology, let us call the nodes that have at least half their neighbors carrying +1, the &quot;infected&quot; nodes. These are the ones that contribute to $N$. One approach is to consider a maximal configuration and look at the set $S$ of infected nodes. The one forms balls of some radius R(n) (say ~ log n) around them and try to show that they do not intersect much ...

http://mathoverflow.net/questions/96817/an-optimization-involving-random-graphs passerby51 2012-05-14T14:07:24Z 2012-05-14T14:07:24Z

You are right, they originally considered the model you mentioned. However, it seems easier for me to consider G(n,p) where you pick each potential edge out of 2-subsets of [n] with probability p.

http://mathoverflow.net/questions/96817/an-optimization-involving-random-graphs passerby51 2012-05-13T06:04:18Z 2012-05-13T06:04:18Z

@Anthony: Thanks. Yes, I am primarily interested in an Erdos-Renyi (ER) graph. I stated the problem more generally, in case it is related to a known problem. You can assume an ER graph with p = a/n, where maybe a = O(log n). Also, you can assume s/n &lt; 1/2 and maybe $ s/n \to \gamma (0,1/2)$ as $n \to \infty$. It would be interesting to show that (max N)/n is strictly less than $\gamma$ as $n \to \infty$ with high probability.

http://mathoverflow.net/questions/55783/elementary-question-in-differential-geometry passerby51 2011-02-17T22:33:28Z 2011-02-17T22:33:28Z

Okay. Fair enough. I should thank you, Roy, for the hint. I guess you are implying that since smoothness does not depend on the chart, I have shown that the inclusion map is not smooth. Intuitively there is something non-smooth about that point of the pointed cone. I just wanted to confirm that it can be made into a smooth manifold as above (which if true is odd to me and interesting!) and that what is wrong shows itself for example as the non-smoothness of the inclusion map into R^3. (I was also wondering if it is possible to remedy this somehow or is this in some sense intrinsic.)