User mark meckes - MathOverflow

Answer by Mark Meckes for Non-asymptotic results for bulk of random Wishart matrix

2013-05-03T21:58:41Z

I don't have time for details right now, but you want to look at circa 1990 papers by Alan Edelman and Stanislaw Szarek (independently) on condition numbers of random matrices. For the state of the art (as of 2009) see this blog post by Terry Tao.

Answer by Mark Meckes for A question on the Mahler conjecture

2013-04-29T15:15:44Z

No, it is not known that the minimum is unique, but it is believed to be. In fact, this paper by Kim and Reisner proves that the simplex is (modulo linear equivalence) a strict local minimum; thus the whole conjecture would follow from uniqueness of local minima.

Answer by Mark Meckes for A short question about the DFT matrix

2013-03-26T17:43:18Z

No. For example, there are Hadamard matrices (after rescaling).

Answer by Mark Meckes for Modern developments in finite-dimensional linear algebra

2013-02-28T14:29:39Z

This is a borderline suggestion, both in terms of how "major" it is and timing (does 1931 count as "early" 20th century?), but there is the Gershgorin circle theorem.

Self-dual finite-dimensional complex normed spaces

2013-02-27T18:05:44Z

Suppose $X$ is a complex normed space of dimension 2 or 3 and $X$ is isometrically isomorphic to its dual. Is $X$ a Hilbert space?

Remarks: There are easy counterexamples in the real case, and in higher dimensions one can construct counterexamples from sums of 2-dimensional spaces which are not isometric to their duals. Similarly a 3-dimensional counterexample can be constructed from a 2-dimensional counterexample.

Answer by Mark Meckes for concentration inequality for averages of dependent random variables

2013-02-22T18:40:02Z

Without further assumptions you can't do better than the union bound (which should be $n e^{-\epsilon^2}$ as you've written things). If $X_i$ are identically distributed and the events $(|X_i| > \epsilon_0)$ are disjoint then you get equality in the union bound for the maximum whenever $\epsilon \ge \epsilon_0$. If the $X_i$ are $\epsilon$ times indicators of disjoint sets then you also get equality in the union bound for the sum.

Very little is true for arbitrarily dependent random variables which is both nontrivial and interesting. It's helpful to keep two extreme cases in mind: disjoint support, and all variables exactly equal to each other.

Answer by Mark Meckes for Almost-converses to the AM-GM inequality

2013-02-20T19:53:08Z

It's not precisely what you asked about, but this paper by Gluskin and Milman shows that, for "most" sequences $a_1, \dotsc, a_n$, the AM-GM inequality can be reversed up to a multiplicative constant. The paper contains a number of observations which come closer to directly addressing your question.

Complementation in an extension field

2013-02-10T18:25:27Z

If $E$ is an extension field of $F$, is $F$ necessarily (without assuming the axiom of choice) complemented as a vector subspace of $E$? (Of course the answer is easily yes if the extension is finite.)

The motivation for the question is pedagogical. I'm looking for as elementary as possible (hence no AC) a way of addressing the following basic linear algebra question: if a linear system $A x = b$, with $A$ an $m\times n$ matrix over $F$ and $b \in F^m$, has a solution $x \in E^n$, does it necessarily have a solution in $F^n$?

Elementary applications of linear algebra over finite fields

2013-01-14T17:06:39Z

I'm teaching axiomatic linear algebra again this semester. Although the textbooks I'm using do everything over the real or complex numbers, for various reasons I prefer to work over an arbitrary field when possible. I always introduce at least $\mathbb{F}_2$ as an example of a finite field. To help motivate this level of generality, I'd like to cover some application of linear algebra over finite fields. Ideally it shouldn't make explicit reference to linear algebra or finite fields in its setup, and should require as little background as possible (the students have taken calculus, but not necessarily any other advanced math — in particular applications to group theory are out). I've looked around a little, but haven't found anything so far that requires little enough overhead to fit into a single 50-minute lecture and wouldn't seem either too abstract or too arbitrary to motivate such students. Any suggestions?

Alternatively, I'd be interested in elementary applications of linear algebra over any other field which isn't a subfield of $\mathbb{C}$.

Answer by Mark Meckes for minimum of different independent Poisson random variables

2012-12-13T19:46:28Z

For large $N$ asymptotics, you want to look into extreme value theory. In particular, take a look at this book.

Answer by Mark Meckes for When does the limit of moments of multivariate distributions determine the limit distribution?

2012-12-13T15:28:46Z

Yes, without any additional assumptions — the relevant technical conditions are satisfied because your limit distribution is normal. For sufficiency in the univariate case, see any probability textbook that covers the method of moments, for example section 30 of Billingsley's Probability and Measure. The multivariate case follows from the univariate case by the Cramér–Wold device, see for example section 29 of Billingsley.

Answer by Mark Meckes for A Wirtinger-like inequality involving two functions

2012-12-11T19:00:34Z

Your inequality is implicit in Hurwitz's Fourier series proof of the isoperimetric inequality in the plane. See for example section 36 of Körner's Fourier Analysis or section 4.1 of Groemer's Geometric Applications of Fourier Series and Spherical Harmonics.

Answer by Mark Meckes for Comparison of the L_p norm of a matrix and its entry-wise absolute value

2012-11-06T16:10:46Z

Okay, so it's established that $\| A \|_p$ means the induced norm. A few basic facts: $$ \| A \|_1 = \max_{j} \sum_{i} |a_{ij}| \le n^{1-1/p} \| A \|_p, $$ $$ \| A \|_\infty = \max_{i} \sum_{j} |a_{ij}| \le n^{1/p} \| A \|_p, $$ $$ \| A \|_p \le \|A\|_1^{1/p} \| A \|_\infty^{1-1/p}. $$ The first two lines are elementary (the inequalities following from standard comparisons of $\ell_p$ norms for vectors), and the third is a finite-dimensional version of the Riesz–Thorin theorem. Putting these together, $$ \|A'\|_p \le \| A' \|_1^{1/p} \| A' \|_\infty^{1-1/p} = \| A \|_1^{1/p} \| A \|_\infty^{1-1/p} \le n^{\frac{2}{p}(1- \frac{1}{p})} \|A\|_p. $$

When $p = 2$ and $A$ is a Hadamard matrix this is sharp, and of course it's sharp for $p=1$ or $p = \infty$. I'd guess it's sharp always but I haven't thought about it.

As noted by Pietro, $\| A \|_p \le \| A' \|_p$ always.

Answer by Mark Meckes for Berry Esseen inequality for multidimensional distributions

2012-10-29T17:28:39Z

There are many results along those lines in Bhattacharya and Rao, Normal Approximation and Asymptotic Expansions.

Answer by Mark Meckes for minimum of two probability densities

2012-09-18T17:54:45Z

One easy sufficient condition (though not necessarily useful or natural, depending on what you know about $\pi$) is $\int \sqrt{\pi(u)} \ du < \infty$, since $\min(a,b) \le \sqrt{ab}$ for $a,b \ge 0$.

Answer by Mark Meckes for Symmetries of probability distributions

2012-09-04T15:38:46Z

I don't know of any systematic study of such symmetries in any great generality. On the other hand, as in most (if not all) fields of mathematics, probability theory happily exploits symmetries to help solve more concrete problems. For example, if $X$ is a random variable and $\xi$ is a bijective solution of your (1), then $X' = \xi(X)$ is a new random variable with the same distribution as $X$, coupled to $X$ in a nontrivial way, which can be a helpful technical tool. In particular, if $\xi\circ \xi = \mathrm{id}$, then $(X,X')$ is an exchangeable pair, which can be used together with Stein's method to prove distributional approximation theorems for $X$.

In a similar vein, your example for Haar measure is essentially the definition of Haar measure, and as such can of course be used (frequently quite directly) to prove many things about Haar measures.

Answer by Mark Meckes for Recent impressive combinatorial developments in probability theory

2012-07-28T12:50:55Z

While it goes back more than a decade, I think Talagrand's "generic chaining"/"majorizing measures without measures" approach to bounding suprema of stochastic processes could be considered a striking development along those lines. (It's definitely striking; the subjectivity is in how "combinatorial" you consider the generic chaining to be.)

Answer by Mark Meckes for Convergence of Fourier series for $C^p$ functions

2012-07-16T15:31:57Z

There is a theorem of Lebesgue that says that for a continuous periodic $f$, $$ \|f - S_N f\|_\infty \le C \log N \|f - f^* \|_\infty. $$ This appears as Theorem 2.2 in Rivlin's book. Combined with the result you already know, you get what you want.

Example of a compact homogeneous metric space which is not a manifold

2011-02-24T14:58:23Z

A metric space $(X,d)$ is isometrically homogeneous if its isometry group acts transitively on points, i.e., for every $x,y \in X$ there is an isometry $\varphi:X\to X$ with $\varphi(x) = y$. I'd like to know an example of a compact isometrically homogeneous metric space which is not a manifold (a space with finitely many points counts as a 0-dimensional manifold).

Googling a bit I've discovered enough recent literature on this general subject to be sure there must be classical examples known to experts, but I haven't managed to find them written down. For example, Theorem 1.2 of this paper implies:

A compact isometrically homogeneous metric space is a finite-dimensional manifold if and only if it is locally contractible.

So equivalently, I'd like an example of a compact isometrically homogeneous metric space which is not locally contractible.

Added: Pete and Neil both gave very nice answers. I'm accepting Neil's since, as Pete points out, it essentially contains Pete's answer as a special case.

Topics for a matrix analysis course

2011-04-04T14:01:36Z

I recently taught a new (to my department) course titled "Matrix Analysis". For various reasons that I won't go into here, I was dissatisfied with the textbook I (loosely) followed, and with every other textbook on the subject I've looked at. The next time I teach the class I will just follow my own notes, which I'm rewriting from scratch. Some of the vital characteristics of the class are the following:

It aims to be accessible and useful to a wide variety of students: grad students and advanced undergrads in pure and applied math, engineering grad students, and possibly others. Particular interests of faculty and grad students in my department which it aims to support include functional analysis, numerical analysis, and probability.
The prerequisite is one semester of linear algebra (although, with the point above in mind, I don't want to assume too much about exactly what that course includes).
As indicated by the title, the emphasis is on analytic aspects of linear algebra and matrix theory -- i.e., those involving convergence, continuity, and inequalities -- as opposed to more algebraic aspects.

Here's my question:

What topics do you think such a class should include, but might not?

The latter part of the question is just to exclude no-brainers like SVD and the Courant-Fischer min-max theorem. I'm especially looking for things that make you think, "Everyone should know about X. Why isn't it ever taught in classes?" Of course I already have in mind some topics of this sort, but by their very nature there are surely many other such topics I'd never think of on my own.

Answer by Mark Meckes for multivariate Gaussian approximation in total variation distance

2012-04-27T22:23:07Z

Stein's method doesn't give total variation approximation in one dimension, either, without some kind of additional assumptions. This has nothing to do with Stein's method; for an impossibility result, any discrete distribution has maximal (1 or 2 depending on your normalization convention) total variation distance to any continuous (e.g. Gaussian) distribution. But of course you can approximate any distribution by a discrete distribution, in Wasserstein distance for example.

Answer by Mark Meckes for Least singular value gaussian orthogonal ensemble.

2012-02-29T20:09:01Z

I'm not sure offhand (and don't have time to check at the moment) if the GOE version of this is known, but the distribution least singular value of a nonsymmetric $n \times n$ matrix with i.i.d. normal entries was determined exactly by Edelman in this paper (may be behind a pay-wall).

Answer by Mark Meckes for marginal log-concave distributions and joint log-concave distributions

2012-02-13T14:52:45Z

No. Let $X$ be, say, a standard normal random variable, $Z$ an independent random variable with $P[Z=1] = P[Z=-1] = 1/2$, and $Y=XZ$. Then $X$ and $Y$ are uncorrelated standard normal (in particular log-concave) random variables, but the distribution of $(X,Y)$ is not log-concave.

This is of course also a counterexample to the false theorem one sometimes hears stated that "uncorrelated normal random variables are independent." (The theorem becomes true if "jointly" is inserted in the right place.)

Answer by Mark Meckes for Derandomizing random matrices

2012-02-06T19:59:32Z

There is active interest in such results in high-dimensional geometry, and expander graphs have even been used explicitly as a tool. Take a look for example at this paper and the references on the second page.

Added: After prodding from the OP, here are some more references to various results of this type. If this question manages to recapture Bill Johnson's attention, maybe he'll contribute some more that I didn't think of.

Here is a survey paper by Davidson and Szarek ending with a short section on derandomizing various constructions. As the Indyk–Szarek paper I linked to above shows, the discussion of Kashin-type results is definitely out of date, but it also has references to work on approximation of quasidiagonal operatrors and approximately free (in the sense of free probability) matrices; I don't know the state of the art on those things.

Other results on reducing randomness in Kashin-type theorems (not all cited by Indyk–Szarek) followed this paper by Schechtman; try a Google Scholar or MathSciNet search of the papers citing it.

This paper by Artstein-Avidan and Milman includes results on reducing randomness in a number of different theorems in geometric functional analysis.

As I said in comments below, randomness reduction is a hot topic in compressed sensing, and not being an expert in the area I don't dare try to guess at the quickly-moving state of the art.

All of the above results, although not necessarily explicitly stated that way, can of course be phrased in terms of properties of some matrices (e.g., identifying a subspace with a matrix whose columns are a basis for the subspace).

Answer by Mark Meckes for Sampling uniformly from a sphere

2012-02-08T17:31:43Z

If by uniform measure you mean $(n-1)$-dimensional Hausdorff measure on the sphere, the answer is no. As a consequence of the results of this paper by Barthe, Csörnyei, and Naor, under mild regularity assumptions the only measure on the boundary of any convex body which can be generated in this way is the "cone measure" on the $\ell_p$ sphere for $1 \le p < \infty$, which coincides with uniform measure only for $p=1,2$.

Answer by Mark Meckes for Random vector of fixed entry-sum

2012-02-06T14:45:38Z

For the expected norm see equation (19) in this paper (or equation (12) in the published version of that paper), which, after some renormalizing, states that $$ \mathbb{E} x_1^{r_1} \cdots x_n^{r_n} = \frac{(n-1)! r_1! \cdots r_n!}{(r+n-1)!}, $$ where $r_i \ge 0$ and $r = r_1 + \cdots r_n$. So in particular (if you can trust my arithmetic) $$ \mathbb{E} ||x||^2 = \frac{2}{n+1}, \quad \mathbb{E} ||x||^4 = \frac{4(n+5)}{(n+1)(n+2)(n+3)}. $$ From these standard Hölder's inequality estimates give that $\mathbb{E} ||x||$ is of order $n^{-1/2}$.

For concentration of the norm, there are general concentration results for convex bodies that apply, in particular "Borell's lemma" which gives much sharper concentration than you asked for — see this answer to another question.

Other relevant results are in this famous paper of Diaconis and Freedman.

Answer by Mark Meckes for Traceless GUE : Four Centered Fermions

2012-01-30T14:32:20Z

Folkmar's answer gives much more detailed information, but here's a more quick-and-dirty answer. Assuming I'm reading your normalization right, for you the diagonal entries of $H$ are $N$ i.i.d. standard normal random variables, and it is $N^{-1/2} H$ which has an approximately semicircular eigenvalue distribution. I'll write $H' = H - N^{-1} \operatorname{tr} (H)$. Then, using $\lambda_j$ to denote the $j$th largest eigenvalue, $$ \lambda_j(N^{-1/2} H') = \lambda_j(N^{-1/2} H) + N^{-1}Z, $$ where $Z = N^{-1/2}\operatorname{tr}(H)$ is a standard normal random variable. Starting from here it's easy to see that the eigenvalue distributions of $N^{-1/2}H'$ and $N^{-1/2}H$ have the same limit.

This argument, unlike the one from the Tracy–Widom paper, also generalizes (using some version of the law of large numbers) to much more general Wigner ensembles.

Answer by Mark Meckes for Does complete monotonicity of f imply log-concavity of f?

2012-01-25T19:00:49Z

A counterexample in the second case is $f(x) = e^{1/x}$. A counterexample in the first case is then $f(x) = e^{1/(x+1) - 1}$.

Answer by Mark Meckes for Löwner-John Ellipsoid: incribed and circumscribed

2012-01-21T21:59:19Z

Q1: Most often it is the maximal volume ellipsoid contained in $K$.

Q2: (a) John's theorem implies that $E^+ \subseteq d E^-$ in general, and $E^+ \subseteq \sqrt{d} E^-$ if $K$ is centrally symmetric, and both these inclusions are sharp (consider a simplex or a cube, respectively), giving of course $d^d$ and $d^{d/2}$ for the best possible upper bounds on the ratios of volumes in the nonsymmetric and symmetric cases respectively.

(b) Not that I'm aware of, but there certainly may be some.

The friendliest reference I can think of is K. Ball, "An elementary introduction to modern convex geometry".

Answer by Mark Meckes for spectra of VERY sparse random matrices

2012-01-20T18:16:45Z

Here's just one quick remark (a little involved for a comment) about how you can start making greater use of your suggested reduction to $A$. Since $M-A$ has rank 1, $$ \sigma_3(A) \le \sigma_2(M) \le \sigma_1(A). $$ Classical results imply that $\sigma_1(A), \sigma_3(A) \approx \sqrt{pn}$, so $\sigma_2(M) \approx \sqrt{pn}$ too.

For more, this paper by Van Vu probably (I haven't read it yet) has a lot that's relevant to your questions.

Comment by Mark Meckes

2013-04-29T17:09:54Z

I'm pretty sure that no such partial results are known, not because I'm an expert on the subject but because I've heard a lot of talks (including quite recently) on the subject and I've never heard any such results. Also in the symmetric case, it's believed that Hanner polytopes are the only minimizers, but I've never heard of any results bounding the number of minima.

Comment by Mark Meckes

2013-03-19T14:00:42Z

What are $S_+$, $S_{++}^n$, and $S^n$?

Comment by Mark Meckes

2013-03-18T16:48:55Z

Going back to Gérard's comment: without having thought all the way through the details, I'm pretty sure that tensorizing regular polygons with $\mathbb{C}$ in the two obvious ways doesn't produce counterexamples: the sets of extreme points of unit balls seem to have different topology. In the case of the complex $\ell_1^2$ and $\ell_\infty^2$ norms (which I am sure of), the sets of extreme points consist of two disjoint circles, and a two-dimensional torus, respectively.

Comment by Mark Meckes

2013-03-18T16:48:08Z

I asked several people this question at a conference last week. Only one was willing even to state a guess of "not necessarily", but had no counterexample to suggest.

Comment by Mark Meckes

2013-03-14T23:30:17Z

A couple people have emailed me to ask about the $\ell_p$ version I mentioned. It's Corollary 4 in this paper: arxiv.org/abs/math/0503650

Comment by Mark Meckes

2013-03-14T14:56:28Z

Are your $X_i$ uniformly distributed in the ball? If so, you may be able to do better using logarithmic Sobolev inequalities (but I haven't thought through the normalizations to be sure).

Comment by Mark Meckes

2013-03-08T01:42:00Z

You can't, without additional assumptions. Suppose $\mu$ has discrete support, say for example it's a Poisson distribution on $\mathbb{R}$, and $f$ is constant on a neighborhood of each point in the support of $\mu$.

Comment by Mark Meckes

2013-03-04T16:45:45Z

A general bit of advice for answering questions of this kind: calculate the first several values, and enter them into the box here: oeis.org

Comment by Mark Meckes

2013-02-28T15:15:49Z

That is, I don't know whether there is a continuous family of real 2-dimensional examples, or where there are smooth real 2-dimension examples. In dimension four one can achieve both with $\ell_p^2 \oplus_2 \ell_q^2$.

Comment by Mark Meckes

2013-02-28T14:57:40Z

Any norm whose unit ball is a regular polygon gives a real two dimensional example. I don't know if there are others; in particular I don't know whether there is a continuous family of examples, or whether there exist smooth examples. I discussed the problem with Szarek briefly yesterday and he raised the latter question in particular, but neither of us has given it serious thought.

Comment by Mark Meckes

2013-02-28T14:09:10Z

@Bill: Thanks adding the banach-spaces tag. I realized later I should have included that one. I also considered adding the ask-johnson tag, but you had already been here by the time I got to it.

Comment by Mark Meckes

2013-02-27T18:24:58Z

The simplest counterexample is given by the $\ell_1$ and $\ell_\infty$ norms. They are of course dual to each other; they are also isometric to each other only in the real 2-dimensional case.

Comment by Mark Meckes

2013-02-27T17:54:12Z

Unless I'm doing something silly, $\mathbb{R}^3$ equipped with the norm $\sqrt{(|x_1|+|x_2|)^2+|x_3|^2}$ is isometric to its dual.

Comment by Mark Meckes

2013-02-26T14:48:10Z

In addition to the obstacles indicated by Douglas's answer, the kind of result you say you're looking for is far to strong to hope for, without much stronger assumptions on the distributions of $X_{n,k}$, if you really insist on letting A be an arbitrary set. What you described in your comment would be convergence in total variation, which fails to be true if, for example, p1 is a discrete measure. In Berry-Esseen-type results you typically only let A range over all intervals.

Comment by Mark Meckes

2013-02-26T14:43:48Z

With the clarification of the word "interval", for the finite/countable case, the answer is trivially no for measure-theoretic/dimension-theoretic reasons. For the "interesting" case it's hard to come up with an interpretation for which the answer is not trivially yes.