User mr.gondolier - MathOverflow

spectra of VERY sparse random matrices

2012-01-20T18:00:05Z

Consider an $n\times n$ random binary matrix $M$ with i.i.d. entries $m_{ij} \sim {\rm Bernoulli}(p)$, where $p = n^{-\beta}$ with $\beta \in (1,2)$. I am interested in the behavior of the singular value decomposition of $$M = \sum_{i=1}^{rank(M)} \sigma_i u_i v_i',$$ where $\sigma_i$ are ranked in decreasing order.

Some intuitive observation (which might NOT be all true!):

1) By subtracting the mean we can write $M = p {\bf 1} {\bf 1}' + A$, where $A$ has indepedent entries with zero mean and variance $p(1-p)$. Therefore I expect the leading singular vector is approximately parallel to the all-one vector ${\bf 1}$, and the largest singular value is $\sigma_1 \approx p n$. If the SVD of $A$ behaves similarly to that of the usual iid matrices, it is probably true that the second largest singular value of $M$ (i.e., the largest singular value of $A$) is approximately $\sigma_2 \approx \sqrt{p n}$.

2) ~~$rank(M)$ is pretty small: since $\mathbb{P}(\text{the first}~ m \text{ rows are all zero}) = (1-p)^{n m}\geq 1-pmn$. Therefore $rank(M) \leq n^{\beta-1}$ with high probability.~~ This is wrong... this only says that $rank(M) \leq n-n^{\beta-1}$.

Are there any rigorous results about the SVD of this matrix ensemble? Is it true that except for $u_1,v_1$ which are approximately $\frac{1}{\sqrt{n}} {\bf 1}$, the remaining singular vectors are independently and uniformly distributed over $S^{n-1}$?

variational problem under convexity constraints

2011-11-23T03:31:28Z

I wonder if there is any method to compute variational problems subject to certain shape constraints (e.g., convexity, monotonicity, etc.). The literature I found on this topic (which I am no expert in) seem to focus on existence and regularities of the solution.

For example: denote the collection of convex functions on $[-1,1]$ by $\mathcal{C}$. Given a fixed $f \in \mathcal{C}\cap L^2$, compute

$\sup\{|Lf-Lg|: \|f-g\|_2 \leq \epsilon, g \in \mathcal{C}\cap L^2\}$,

where $L$ is some linear functional. To be concrete, let's consider $Lf=f(0)$. When $\epsilon$ is small, $g$ is like a perturbation of $f$, but since $g$ needs to be convex, the perturbation cannot be arbitrary. Even some asymptotic result would be enlightening.

explicit extention of Lipschitz function (Kirszbraun theorem)

2011-05-10T15:49:42Z

Kirszbraun theorem states that if $U$ is a subset of some Hilbert space $H_1$, and $H_2$ is another Hilbert space, and $f : U \to H_2$ is a Lipschitz-continuous map, then $f$ can be extended to a Lipschitz function on the whole space $H_1$ with the same Lipschitz constant.

Now let's take $H_2$ to be the Euclidean space $\mathbb{R}^n$. My question is: Is there way to explicitly construct this extension? Note that the standard proof (e.g. see Federer's geometric measure theory book or Schwartz's nonlinear functional analysis book) is an existence proof, which uses Hausdorff's maximal principle.

Some remarks:
1) For $n = 1$, the extension can be constructed explicitly, which works even if $H_1$ is only a metric space (with metric $d$): $\tilde{f}(x) = \inf_{y \in U} \{ f(y) + {\rm Lip}(f) d(x,y) \}$. See for example Mattila's book p. 100.

2) For $n > 1$, performing the above extension for each component of $f$ results in blowing up the Lipschitz constant by a factor of $\sqrt{n}$.

support of the coupling between two probability measures

2011-03-01T05:29:35Z

Given two Borel probability measures $\mu$ and $\nu$ on $\mathbb{R}$, let $\Pi(\mu, \nu)$ denote all couplings between them, i.e., all Borel probability measures on $\mathbb{R}^2$ such that the marginal distribution of the first and second coordinate are $\mu$ and $\nu$ respectively. Can we describe the set of all possible support of the joint law:

$S(\mu, \nu) = \{E \subset \mathbb{R}^2: \exists \lambda \in \Pi(\mu, \nu), s.t. \lambda(E) = 1\}$.

Strassen (Theorem 11) characterized this collection: $C \in S(\mu, \nu)$ if and only if for all $U$ open in $\mathbb{R}$, $\nu(U) \leq \mu(U^C)$, where $U^C = \{x: \exists y \in U, s.t. (x,y) \in C\}$. But this condition seems not easy to verify! For instance, it is probably not true to only consider open interval $U$.

Let us focus on the normal distribution $\mu=\nu=N(0,1)$. Can we characterize $S' = S(N(0,1), N(0,1))$ more explicitly in this case, i.e., what kind of subset in the plane admits a probability measure whose marginals are standard normal? For instance we can ask the following question: for what pair of $a < b$ do we have $\{(x,y): a \leq |x-y| \leq b\} \in S'$, that is, can we construct a joint distribution on this strip that has standard normal marginals. It seems a non-trivial question. For $b = \infty$, one can show that the largest possible $a$ is between $\sqrt{\pi/2}$ and $3/2$. I am thinking is there a systematic way to do it in the simple case of real line. Note that Strassen's result work for any Polish space.

number of solutions of diophantine approximation

2011-01-07T23:15:34Z

Let $x$ be a real number and $N$ a positive integer. Define

$E(N,\delta) = \{(p,q) \in \mathbb{Z}^2: |p - q x| \leq \frac{\delta}{N}, |p|, |q| \leq N \}$,

i.e., the set of solutions to rational approximation of $x$ with accuracy $\frac{\delta}{N}$.

I am interested in the behavior of the cardinality of $E(N,\delta)$. Question:

For which $x$ do we have $|E(N,\delta)| \leq c(\delta) N$ where $c(\delta) \to 0$ as $\delta \to 0$?

Of course $x$ has to be irrational. Is this true for all irrational $x$? I am very unfamiliar with Diophantine approximation. I googled a bit and found that Schmidt proved that $|E(N,\delta)| = O(\log N)$ for a.e. $x$. Lang proved that this holds for all quadratic irrational $x$. But $O(\log N)$ is much stronger than what I asked, which is even weaker than $o(N)$.

(One further question: if we replace $\frac{1}{N}$ by $\frac{1}{N^{1+\epsilon}}$, how does the number of solutions behave?)

local behavior of a finite Borel measure

2010-11-11T07:19:13Z

Let $\mu$ be a finite Borel measure on $\mathbb{R}^n$. I am interested in how does $\mu(B(x,r))$ behave, where $B(x,r)$ is the open ball of radius $r$ centered at $x$. For instance, as far as I recall, for each $\alpha \in [0,n]$, there exists finite $\mu$ so that $\mu(B(x,r)) \sim r^{\alpha}$ for $\mu$-a.e. $x$, which are called dimensionally-regular measures (with constant local dimension $\alpha$).

Here is my question: does there exist finite Borel measure$\mu$ such that that $\mu(B(x,r))$ vanishes superpolynomially fast, say, $\sim e^{-\frac{1}{r}}$, i.e.,

$\mu\left(\left\{x: \liminf_{r \to 0} r |\log \mu (B(x,r)) | > 0 \right\}\right) > 0$?

Answer by mr.gondolier for Continuity of the mutual information

2010-11-06T20:33:06Z

Mutual information is weak-* lower semicontinuous, because it is Kullback-Leibler divergence. For this see Pinsker's book or Dupuis-Ellis. This gives you the desired liminf. For the other direction (which is usually easy because I haven't used your monotonicity condition yet), maybe you have some monotonicity or convexity argument.

construction of a random measure with a given mean

2010-11-06T03:15:16Z

Let me first pose a trivial question.

Given a Borel probability measure $\mu$ on the real line, is it possible to construct a purely atomic random measure $M$ whose mean is $\mu$?

The answer is obviously yes: take $M = \delta_{X}$, where $\delta_x$ is the Diract measure sitting at $x$ and $X$ is a random variable distributed according to $\mu$. In fact take $M$ to be the empirical measure $\frac{1}{n} \sum_{i=1}^n \delta_{X_i}$ where each $X_i \sim \mu$ suffices.

Now here is my question:

Given a Borel probability measure $\mu$ on the real line and $\delta > 0$, is it possible to construct a purely atomic random measure $M$ whose mean is $\mu$ and $d(M, \mu) < \delta$ almost surely, where $d$ is some metric on the space of probability measures (e.g. the Wasserstein distance, the Lévy–Prokhorov metric or the Kolmogorov distance, i.e., the sup-distance between distribution functions)?

Of course for an arbitrary distance this is not always possible. For example, if $d$ is the total variation distance and $\mu$ is atomless, then $d(M,\mu) = 2$ a.s. But for a weaker distance, will this be possible? The intuition is the following: consider the empirical measure $\frac{1}{n} \sum_{i=1}^n \delta_{X_i}$ where $X_i$ are iid generated from $\mu$. Then as $n\to\infty$, it will converge to the mean $\mu$ a.s. under those distances. Therefore within any $\delta$-ball centered at $\mu$, there are lots of atomic measures, i.e., $\mathbb{P} \{d(M,\mu) < \delta\}$ is very close to 1. But can we achieve exactly 1, i.e., can we construct an $M$ supported on those measures which are close to the desired mean?

Answer by mr.gondolier for construction of a random measure with a given mean

2010-11-06T20:17:28Z

Let $\{ X_n \}$ be an i.i.d. sequence with common law $\mu$. Denote the empirical measure by $L_n = \frac{1}{n} \sum_{i=1}^n \delta_{X_i}$. Define the stopping time $T = \min \{n: d(L_n, \mu) \leq \delta \}$. Then $T < \infty$ a.s. (which follows from Glivenko-Cantelli and LLN if we are considering transport metric like 2-Wasserstein). Therefore $L_T$ is a well-defined random measure, which satisfies $d(L_T, \mu) \leq \delta$ automatically. Moreover, $L_T$ is purely atomic with finitely many atoms almost surely. Observe that $L_T$ has mean $\mu$. To see this, note that for any positive Borel function $f$,

$\mathbb{E}[\int f d L_T]$

$ = \sum_{n \geq 1} \frac{1}{n} \mathbb{E}[\sum_{i=1}^n f(X_i) | T = n] \mathbb{P}\{T = n\}$

$ = \sum_{n \geq 1} \mathbb{E}[f(X_1) | T = n] \mathbb{P}\{T = n\}$

$ = \mathbb{E}[f(X_1)]$

$ = \int f d \mu$

where the second equality is by symmetry.

Answer by mr.gondolier for Lipschitz properties of minima/minimizers of convex functions of two variables

2010-11-05T22:44:35Z

I encountered the same problem three years ago and found some relevant literature. Here are a few. See also the refs therein.

Lipschitz Behavior of Solutions to Convex Minimization Problems. Jean-Pierre Aubin, Mathematics of Operations Research, Vol. 9, No. 1. (Feb., 1984), pp. 87-111.

Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems. O. L. MANGASARIAN and T.-H. SHIAU. SIAM J. CONTROL AND OPTIMIZATION, 25(3), 1987.

Lipschitz Continuity of Solutions of Variational Inequalities with a Parametric Polyhedral Constraint. N. D. Yen, Mathematics of Operations Research, Vol. 20, No. 3. (Aug., 1995), pp. 695-708.

On Lipschitzian Stability of Optimal Solutions of Parametrized Semi-Infinite Programs. Alexander Shapiro, Mathematics of Operations Research, Vol. 19, No. 3. (Aug., 1994), pp. 743-752.

SHARP LIPSCHITZ CONSTANTS FOR BASIC OPTIMAL SOLUTIONS AND BASIC FEASIBLE SOLUTIONS OF LINEAR PROGRAMS. Wu Li, SIAM J. CONTROL AND OPTIMIZATION Vol. 32, No. I, pp. 140-153, January 1994

estimate the error term in CLT

2010-09-19T10:02:28Z

Let $X_m = \frac{1}{\sqrt{m}}\sum_{k=1}^m Z_k$ where $Z_k$ are iid equally likely on $\{\pm 1\}$. Then $X_m$ convergens to $X \sim \mathcal{N}(0,1)$ in distribution by CLT.

Let $f$ be a smooth bounded function on $\mathbb{R}$. Then $\mathbb{E}[f(X_m)] \to \mathbb{E}[f(X)]$. I wonder if there is any general method to give sharp asymptotic estimate of the error term $\mathbb{E}[f(X_m)] - \mathbb{E}[f(X)]$, which I expect to be $\Theta(1/m)$. The scaling constant should depend on $f$ (as well as the distribution of $Z_k$ if they are not binary).

For law of large number, this type of estimate can be done via the Delta method (e.g., to estimate $\mathbb{E}[f(\bar{Z})] - f(0)$). There must be a counterpart for CLT... I haven't found the Edgeworth expansion useful because it seems to work with distribution with densities.

Edited: To be clear, I am only interested in some specific nice function (e.g., $f(x) = x^2 e^{-x^2/4}$) and finding a sharp expansion for the error term of the form, say, $c/m + o(1/m)$, where $c$ will depend n $f$. As pointed by Mark, the worst-case rate of all bounded smooth function $f$ is $1/\sqrt{m}$, which agrees with the upper bound given by Stein's method.

Answer by mr.gondolier for estimate the error term in CLT

2010-09-20T15:42:53Z

Sorry this is NOT an answer to my question... just some clarafications.

The reason I think $m^{-1/2}$ is not tight is as follows. For example, take $f$ to be the characteristic function, we have

$\mathbb{E}[e^{itX_m}] = (\mathbb{E}[e^{it Z/\sqrt{m}}])^m = (1 - t^2/(2m) + o(1/m))^m \to e^{-t^2/2} = \mathbb{E}[e^{itX}]$

at rate $1/m$, because $m\log(1-1/m) \to -1$ at rate $1/m$.

Also, it seems all moments of $X_m$ converge to the moments of $X$ at rate $1/m$. Doing a Taylor expansion for those nice $f$ should also yield a rate of $1/m$?

modular arithmetic of Hermite polynomials

2010-08-16T08:10:16Z

I wonder if there is anything known (formula, asymptotics, etc) of computing the remainder

$R_{k,m} \equiv H_{k} ~ \mod H_m$

for $k > m$, where $H_m$ denotes the $m$th Hermite polynomial (orthogonal under the weight $w(x) = e^{-x^2}$) and $\deg R_{k,m} \leq m-1$. I haven't been able to find anything online, neither could compute it through the recurrence relation of Hermite polynomials...

Update:

The motivation for my question is as follows. The $m$-point Gauss-quadrature is obtained by placing the nodes at the roots of $H_m$ and choosing the weights accordingly such that integrating any polynomial (with respect to weight $w$) of order $\leq 2m-1$ is exact. Now I want to know the error formula for polynomials of degree $k \geq m$, especially $H_k$. By computing $H_k$ modulo $H_m$, the integration error is given by the integration of the remainder $R_{k,m}$.

Asymptotics of Hermite and hypergeometric function

2010-08-15T12:32:23Z

I am looking for the asymptotics of the following integral

$\int_{\mathbb{R}} H_m^2(x) {\rm e}^{-2 \alpha^2 x^2} {\rm d} x = 2^{m-1/2} \alpha^{-2m -1} (1-2\alpha^2)^m \ \Gamma(m+1/2) ~ _2F_1\left(-m,m,1/2-m,\frac{\alpha^2}{2\alpha^2-1}\right)$

where $H_m$ is the $m^{\rm th}$ Hermite polynomial (orthogonal under the weight ${\rm e}^{-x^2}$), and $_2F_1$ is the hypergeometric function.

I found this formula from p. 803 of "Table of Integrals, Series, and Products" by Gradshteyn-Ryzhik. However, I have idea about the asymptotics of the $_2F_1$ term. Can anyone enlighten me on the asymptotics of

$_2F_1\left(-m,m,1/2-m,\beta\right)$

when $m$ is large? In fact I tried mathematica and it seems $_2F_1\left(-m,m,1/2-m,\beta\right) \sim |4 \beta|^m$. Any reference on this issue?

Now given the above asymptotics is true, observe that the norm of $H_m$ under the weight ${\rm e}^{-2 \alpha^2 x^2}$ has the same exponent for all $alpha$, including the original weight ($\alpha^2 = 1/2$). Is this a common phenomenon for orthogonal polynomials?

Answer by mr.gondolier for Product Measure Only Possible Measure?

2010-08-29T07:19:59Z

Every such a $\nu$ is the law of some stationary process on $X^{\mathbb{Z}}$. Of course not every stationary process is i.i.d.

convergence of a series involving cosines

2010-08-24T06:02:18Z

Question:

1) How to determine the convergence of

$\displaystyle \sum_{k=1}^{\infty} \frac{\cos(k^{\alpha} x)}{k^{\alpha}} (-1)^k $

where $x \in \mathbb{R}$ and $\alpha \in (0,1]$. I am especially interested in the case of $\alpha = 1/2$.

2) For a fixed $\alpha$, if the above series converges for every $x$, is the convergence uniform? Is the resulting sum bounded in $x$?

I found the series tests (alternating test,etc.) I learned not useful in this situation, except that the convergence is clear for $x = 0$...

Point cloud that maximizes the minimum pairwise distance in Euclidean space

2010-08-09T04:56:43Z

I am interested finding the collection of points in the Euclidean space that has the maximal minimal pairwise distance subject to an average norm constraint, that is, how to maximize

$min_{i \neq j} |x_i - x_j|$

subject to $\frac{1}{n} \sum_{i=1}^n |x_j|^2 \leq1$ where $\{x_1, \ldots, x_n\} \subset \mathbb{R}^d$.

I wonder if this problem has a name and what is known about it. Of course $d = 1$ is easy: just choose $n$ uniformly spaced points that satisfies the constraint with equality. I am especially interested in $d=2$. If little is known in the non-asymptotic case, maybe we know more when $n$ and/or $d$ is large? Is it related to sphere packing?

(BTW, I heard that the answer is given by vertices on the simplex when $n \leq d -1$ (or maybe the other way around?))

Minimizing quadratic form over permutations

2010-08-03T05:32:20Z

Let $Q$ be an $n \times n$ real symmetric matrix and $x$ an $n \times 1$ real vector. Consider the following minimization problem:

$\min_{\pi \in S_n} ~(\pi x)^{\rm T} Q (\pi x)$,

where $S_n$ denotes the collection of all permutations on $x$.

I wonder if there is any sufficient condition on the matrix $Q$ that guarantees that the solution is given by the permutation that puts $x$ in increasing order. For instance, such a $Q$ qualifies: $Q = \left(\begin{matrix} 0 & -1 & 0 & 0 \\ -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 \\ 0 & 0 & -1 & 0\end{matrix}\right)$. Does it have anything to do with majorization theory?

P.S., I googled a bit and it seems this is a particularization of the so-called quadratic assignment problem. There are a lot of discussions dealing with complexity of finding the solution. I wonder if we can we come up with some sufficient condition to guarantee that the optimal solution is to simply perform a sort.

Indexing schemes of binary sequences

2010-07-13T22:04:33Z

I am looking for "low-complexity" indexing methods to enumerate binary sequences of a given length and a given weight.

Formally, let $T_k^n = \{x_1^n \in \{0,1\}^n: \sum_{i=1}^n x_i = k\}$. How to construct a bijective mapping $f: T_k^n \to \{1, 2, \ldots, \binom{n}{k}\}$ such that computing each $f(x_1^n)$ needs small number of operations?

For example, one could do lexicographical ordering, that is, e.g., $0110 < 1010$. Then this gives the following scheme:

$f(x_1^n) = \sum_{k=1}^n x_k \binom{n-k}{w_k}$

where $w_k=\sum_{i=k}^n x_i$. Computing $n$ binomial coefficients can be quite demanding. Any other ideas? Or is it impossible to avoid?

Constructive aspects of Caratheodory's theorem in convex analysis

2010-05-17T19:45:42Z

Let me paraphrase Caratheodory's theorem in a probabilistic setup:

Let $X$ be a real-valued random variable. For $k = 1, \ldots, m$, let $f_k: \mathbb{R} \to \mathbb{R}$ be a continuous function such that $\mathbb{E}[f_k(X)]$ is finite. There exist a discrete real-valued random variable $Z$ with at most $m+1$ atoms, such that:

(1) $\mathbb{E}[f_k(X)] = \mathbb{E}[f_k(Z)]$ for $k = 1, \ldots m$.

This is a simple consequence of Caratheodory's theorem in convex analysis, because the point $P = (\mathbb{E}[f_1(X)], \ldots, \mathbb{E}[f_m(X)])$ belongs to the convex hull of the set $E = \{(f_1(x), \ldots, f_m(x)): x \in \mathbb{R} \} \subset \mathbb{R}^m$. Therefore $P$ can be written as a convex combination of at most $m+1$ points in $E$.

The above is an existence result. Here are my questions:

1) Given the density of $X$ and $f_1, \ldots, f_m$, is there an efficient algorithm to compute the location and weights of $Z$? I know how to do this when polynomials are concerned, i.e., $f_k(x) = x^k$. As elucidated by fedja in reply to a question I asked before, this problem is solved by the Gaussian quadrature, and the locations are given by roots of orthogonal polynomials. The problem I am facing is for standard normal $X$ and $f_k(x) = \exp(-x^2) x^k$. I do not have a clue how to solve this highly nonlinear problem.

2) Let us take a closer look at the special case when $f$'s are monomials. In this case what Gaussian quadrature achieves is twice better than Caratheodory's theorem, namely, $(m+1)/2$ atoms are enough to satisfy (1). This number is optimal intuitively, because we have $m+1$ equations to solve: $m$ equations in (1) and weights sum up to one. Hence we need at least $m+1$ "degrees of freedoms", half being locations and half being weights. (My friend told me this can be made precise by algebraic geometry, though I do not understand). I wonder what is so special about polynomials in this problem. I do not suppose Caratheodory's theorem can be improved by a factor of two. For non-polynomial functions, like those in my first question, is $m+1$ really necessary?

approximate a probability distribution by moment matching

2010-04-08T21:46:53Z

Suppose we want to approximate a real-valued random variable $X$ by a discrete random variable $Z$ with finitely many atoms. Suppose all moments of $X$ is finite. We want to match the moments of $X$ up to the $m^{\rm th}$ order:

(1) $\mathbb{E}[X^k] = \mathbb{E}[Z^k]$ for $k = 1, \ldots m$.

Here is a positive result, which is a simple consequence of convex analysis (Caratheodory's theorem): there exists $Z$ with at most $m+1$ atoms such that (1) holds.

Here are my questions:
1) Is there a converse result about this? Say $X$ has an absolutely continuous distribution supported on $\mathbb{R}$ (e.g. Gaussian). When $m$ is large, given that $Z$ has only $m$ atoms, can we conclude that we cannot approximate all $2m$ moments of $X$ well, i.e., can we lower bound the error $\max_{1 \leq k \leq 2m}|\mathbb{E}[X^k] - \mathbb{E}[Z^k]|$? My intuition is the following: for a Gaussian $X$, $\mathbb{E}[X^k]$ grows like $k^{\frac{k}{2}}$ superexponentially. When we find a $Z$ who matches all moments of $X$ up to $m$, it cannot catch up with higher-order moments $X$; if $Z$ matches all moments from $m+1$ up to $2m$, then its low-order moments will be quite different from $X$.

2) Is there an efficient algorithm to compute the location and weights of the approximating discrete distribution? Does there exist a table to record these for approximating common distribution (e.g. Gaussian) for each fixed $m$? It could be very handy...

3) I heard from folklore that when (1) holds, the total variation distance between their distributions can be upper bounded by, say, $e^{-m}$ or $1/m!$. Of course, this won't be true for a discrete $Z$. But let's say $X$ and $Z$ both has smooth and bounded density on $\mathbb{R}$. Could this be true? Now two characteristic functions matches at $0$ up to $m^{\rm th}$ derivatives. They should be pretty close?

continuous selection of a multivalued function?

2010-04-06T03:02:02Z

The title is probably a bit too broad. I frequently encountered the following situation: suppose I need to select a solution to a linear equation from a compact set. Can I make this selection continuous?

Formally, let $S \subset \mathbb{R}^n$ be a compact set. Let $A$ be a $k \times n$ matrix ($k < n$), which we view as a linear function $A: \mathbb{R}^n \to \mathbb{R}^k$. Let $T = A(S)$ be the range of $A$ on $S$. Is there a continuous function $g: T \to S$, such that $A g(y) = y$?

To construct $g$, we only need to pick a value from the solution set $A^{-1}(\{y\}) \cap S$, which is compact. The question is: can we choose it in a continuous way? It is easy to see that we can choose $g$ to be Borel measurable, say, choose $g$ to be the one with the minimum Euclidean norm from the solution set.

how slow can the dimension of a product set grow?

2010-03-19T00:29:16Z

Let us define the following "dimension" of a Borel subet $B \subset \mathbb{R}^k$:

$\dim(B) = \min\{n \in \mathbb{N}: \exists K \subset \mathbb{R}^n, ~{\rm s.t.} ~ B \sim K\}$,

where $\sim$ denotes "homeomorphic to". Obviously, $0 \leq \dim(B) \leq k$.

I have three questions: Given a $B \subset \mathbb{R}$,
1) As $k \to \infty$, how slow can $\dim(B^k)$ grow? Can we choose some $B$ such that $\dim(B^k) = o(k)$ or even $O(1)$?
2) Will it make a difference if we drop the Borel measurability of $B$ or add the condition that $B$ has positive Lebesgue measure?
3) Does this dimension-like notion have a name? The dimension concepts I usually see are Lebesgue's covering dimension, inductive dimension, Hausdorff dimension, Minkowski dimension, etc. I do not think the quantity defined above coincides with any of these, but of course bounds exist.

Thanks!

Answer by mr.gondolier for Determining a lower bound on the Hausdorff dimension of a set

2010-03-04T19:59:25Z

There are lower bound based on potential theoretic methods. Still, you need to have a measure $\mu$ supported on your set $E$. Define the $s$-energy of $\mu$ as

$I_s(\mu) = \iint |x-y|^{-s} \mu({\rm d} x) \mu({\rm d} y)$

If $I_s(\mu) < \infty$, then $\dim_{\rm H} (E) \geq s$. [Theorem 4.13, Falconer Fractal Geometry 2nd Ed.] IIRC, the proof follows from the density-based lower bound that Gerald gave. But if your measure allows easy estimate of potential, then it might be more convenient.

Moreover, you have the following characterization of Hausdorff dimension:

$\dim_{\rm H} (E) = \inf \{ s \geq 0 : C_s(E) = 0 \} = \sup \{s \geq 0 : C_s(E) > 0\}$,

where $C_s(E)$ is the $s$-capacity of $E$, defined as

$C_s(E) = \sup\{I_s(\mu)^{-1}: \mu \text{ is a probability measure supported on }E \}$

There are also lower bounds based on the Fourier transform of $\mu$. See Sec. 4.4 of Falconer's book.

Can we extract information about how fast a function decay from its Laplace transform?

2010-02-19T03:39:33Z

My question is whether we can extract information about how fast an integrable function converges to zero by looking at the asymptotics of its Laplace transform.

More concrete case, let $f:\mathbb{R} \to \mathbb{R}_+$ be a smooth function in $L^1(\mathbb{R})$. If we know that its Laplace transform exists on the positive real axis and:

$\int_{\mathbb{R}} f(x) e^{sx} {\rm d}x \geq e^{\frac{s^2}{2}}, \quad \forall s > 0$,

can we conclude that the speed that $f$ converge to zero cannot be faster than $e^{-\frac{x^2}{2}}$, say,

$\liminf_{|x| \to \infty} \frac{f(x)}{e^{\frac{-x^2}{2} (1 - \epsilon)}} > 0$

for some small $\epsilon \in (0, 1)$? In a more probabilistic setup, if we know the moment generating function is lower bounded by that of Gaussian, can we conclude that it is "super-Gaussian"? I know that the other direction seems to be true and is called sub-Gaussian.

If the information on the right-half real axis is not enough, do we need to know more? Will Fourier transform be more helpful? How about the other direction, i.e., lower bound on the Laplace transform and upper bound on the decay of $f$? Thanks.

"exchange" of real analyticity and integration

2010-02-15T04:40:19Z

Sorry for the impreciseness of the title. It is merely meant for an analogy.

Exchange of limiting operations and integrations are basically derived from Lebesgue's dominated convergence theorem. For instance, let $f: \mathbb{R}^2 \to \mathbb{R}$ be Borel measuable. Let $f(\cdot, u) \in C^k(I)$ for some open set $I$ and for all $u$ in a Borel set $D$. Let

$g = \int_D f(x,u) {\rm d} u$.

Then a sufficient condition for $g \in C^k(I)$ is that $f^{(k)}(x, \cdot)$ is dominated by an integrable function on $D$, i.e., $\sup_{x \in I} |f^{(k)}(x, \cdot)| \in L^1(D)$, and $g^{(k)}(x) = \int_D f^{(k)}(x,u) {\rm d} u$ holds in $I$.

My question is about when is real-analyticity preserved under integration, say, if $f$ is real-analytic in $I$ for each $u$, i.e., $f(\cdot, u) \in C^{\omega}(I)$ for all $u \in D$, what will be a sufficient condition for $g \in C^{\omega}(I)$?

Following the above rationale, we will obtain the following condition: for each $x_0 \in I$,
1) the radius of convergence of $f(x, u) = \sum_k a_k(u) (x-x_0)^k$ is bounded away from zero for all $u \in D$.
2) integrability condition: $\int_D \sum_k a_k(u) (x-x_0)^k {\rm d} u < \infty$. Then the analyticity of $g$ follows from Fubini's theorem.

Questions:
1) Is there other sufficient condition different from the above 'superficial' generalization, maybe exploring other characterization of real analyticitiy? The absolute integrability might not be easy to check.
2) Is there a more local version, which might give the radius of convergence of $g$.

Thanks!

How to estimate the growth of a recurrence sequence

2010-02-14T06:56:35Z

If we have a linear recurrence sequence where each term depends on all previous terms, say

$a_n = \sum_{k=0}^{n-1} \binom{n}{k} a_k, \quad a_0 = 1$

is there any way to estimate the growth of a_n in terms of a Big-O notation?

I suppose the growth must be super-exponential, because if $a_1, \ldots, a_{n-1}$ grows exponentially, say, $q^i$, then we have $a_n = (q+1)^n - q^n$. Hence The exponent grows from $q$ to $q+1$. But I am not sure if this serves as an argument.

Thanks!

convergence rate in Wiener's approximation theorem

2010-02-03T03:26:55Z

Wiener has the following fantastic results about approximations using translation families:

Given a function $h: \mathbb{R} \to \mathbb{R}$, the set $\{\sum a_i h(\cdot - x_i): a_i, x_i \in \mathbb{R}\}$ is

i) dense in $L^1(\mathbb{R})$ if and only if the Fourier transform of $h$ has no zeros.
ii) dense in $L^2(\mathbb{R})$ if and only if zeros of the Fourier transform of $h$ has zero Lebesgue measure.

After this, a further step is natually about the speed of convergence, i.e., how fast does the error vanishes with respect to the the number of translates. Now let us focus on the $L^1$ case and take $h = \varphi$ to be the standard normal density whose Fourier transform does not vanish on the real line. Given a function $f \in L^1(\mathbb{R})$, the error of the optimal $m$-term approximation is

$\mathop{\inf}\limits_{a_i, x_i \in \mathbb{R}} \left\|f - \sum_{i=1}^m a_i h(\cdot - x_i)\right\|_1$.

My question is whether there is any way to lower bound this quantity. Of course, there won't be any meaningful conclusion without assumptions on $f$ (e.g., $f$ is a finite-mixture of translates of $\varphi$, then it is trivial). So let us consider $f = g * \varphi$ for some smooth $g$ (e.g., $g = \varphi$), where $*$ denotes convolution, that is, $f$ is an ``infinite"-mixture of translates of $\varphi$. Any idea would be greatly appreciated. If things could be easier using $L^2, L^{\infty}$ or other distance, it should also be helpful.

For the upper bound, there have been many work, the speed of convergence could be $O(m^{-2})$ or even exponential in $m$. For the lower bound, most work consider a min-max setup: for $f$ belonging to a given class of functions, the worst-case convergence rate can never by faster than $O(m^{-2})$. But for a given $f$, there seems to be no known result.

Answer by mr.gondolier for Approximating with translated Gaussians and low-frequency trig functions

2010-02-03T05:12:42Z

Wiener's approximation theorem says that

Given a function $h: \mathbb{R} \to \mathbb{R}$, the set $\{\sum a_i h(\cdot - x_i): a_i, x_i \in \mathbb{R}\}$ is dense in $L^2(\mathbb{R})$ if and only if zeros of the Fourier transform of $h$ has zero Lebesgue measure.

See Wiener's book "The Fourier Integral and Certain of Its Applications" or Chandrasekharan's "Classical Fourier Transforms".

Further question when the translating parameters are restricted to a smaller set are considered by a series of authors. See this paper for instance and the reference therein.

Comment by mr.gondolier

2012-01-21T01:11:14Z

Also, what do you think about $rank(M)$? Your thesis seems to deal with the case with $p>=\log n / n$, i.e., $\beta \leq 1$ and rank is full whp. Here probably rank is roughly number of non-zero rows/columns?

Comment by mr.gondolier

2012-01-21T01:09:28Z

Thanks Kevin. I understand your calculation of the probability but I didn't quite get what you meant by block decomposition. Can you elaborate a bit?

Comment by mr.gondolier

2012-01-20T18:29:55Z

could you give a bit more details on the classical result, because here the entrywise distribution of $A$ varies with the dimension, so presumably you need some non-asymptotic bounds on $\sigma_{\cdot}(A)$ ?

Comment by mr.gondolier

2012-01-20T18:27:11Z

Thanks! Fixed.

Comment by mr.gondolier

2011-11-23T08:22:04Z

Thanks Pietro! But it does not seem always true: take $f(x)=x$. The obtained $g$ is non-convex? For functions like $f(x)=x^2$, What you suggested should be optimal when $\epsilon$ is small: choose a $g$ composed of two tangent lines and the rest of the parabola.

Comment by mr.gondolier

2011-01-08T04:56:29Z

Many thanks. Now I understood it. The result you mentioned is Theorem 19 of Khinchin. Given that, it remains to show that $q_k = \omega(k)$, where $q_k$ is the denominator of the $k$th convergent of $x$. But since $q_k = a_k q_{k-1} + q_{k-2}$ and $a_k$ is a positive integer, $q_k$ grows at least as Fibonacci, i.e., exponentially. Therefore number of solutions is $O(\log N)$ for all irrational $x$.

Comment by mr.gondolier

2011-01-08T00:50:40Z

Thanks Gerry! I have changed edited it accordingly. Can you elaborate a bit on your point or give a reference? I am not familiar with continued fraction and related things... And by Hurwitz's theorem do you mean this one: mathworld.wolfram.com/…

Comment by mr.gondolier

2010-11-23T06:33:08Z

thanks Pablo! Now I remembered I've seen this theorem from Federer's book before. Somehow I escaped my mind...

Comment by mr.gondolier

2010-11-12T00:19:42Z

Great. The same proof shows that it is impossible to have $\mu(B(x,r)) \sim r^{\alpha}$ for $\alpha > d+1$. I think the tight result should be $\alpha > d$.

Comment by mr.gondolier

2010-11-06T20:19:36Z

it is also related to those sensitivity analysis in convex optimization. see for example chap. 5 of luenberger's red book.

Comment by mr.gondolier

2010-11-06T20:08:39Z

Great! I am accepting it as the answer. I suppose you used the convexity in the last step since $\mu = \sum \mu(I_i) \mu_i$. BTW I have another construction which has finite support almost surely. See my own answer below.

Comment by mr.gondolier

2010-11-06T05:09:56Z

For any Borel function $f$, $\mathbb{E}[\int f dM] = \frac{1}{n} \sum_i \mathbb{E}[f(X_i)] = \mathbb{E}[f(X)] = \int f d\mu$. Therefore $\mu$ is the mean of $M$.

Comment by mr.gondolier

2010-11-05T23:00:22Z

The calculation of characteristic function simply follows from the observation that for Cantor distributed $X$, its ternary expansion is given by $X = \sum_{k\geq1} X_k 3^{-k}$, where $X_k$ are iid and takes values 0 or 2 with equal probability.

Comment by mr.gondolier

2010-09-20T16:36:26Z

I agree that there exists $f$ such that $1/sqrt{m}$ is tight. In fact I am not looking for uniform estimates but rather for a specific function $f(x) = x^2 e^(-x^2/4)$. In my OP, I said the scaling constant will depend on the function $f$. Based also on numerical result, I believe its rate is $1/m$. Do you think there is any method to produce a sharp expansion of the form $c/m + o(1/m)$? Any lower bound idea?

Comment by mr.gondolier

2010-09-20T15:42:37Z

Mark, thanks for your reply. See my example below. Maybe I made a mistake?