User alex gittens - MathOverflow

relationship between numerical and spectral radii for product of positive definite matrices?

2013-04-23T21:42:37Z

The original problem I'm looking at is: given a bound on the operator norm of $\Lambda A \Lambda,$ where $\Lambda, A$ are positive definite matrices and $\Lambda$ is diagonal, what is the tightest bound on the operator norm of $A \Lambda^2.$

My starting point is the fact that these two matrices have the same eigenvalues, so the operator norm of $\Lambda A \Lambda$ upper bounds the spectral radius of $A \Lambda^2.$

For normal matrices, the numerical radius is the same as the spectral radius and the operator norm. While $A \Lambda^2$ is not normal, one might hope that it is nice enough that there is still some nontrivial connection between its numerical and spectral radii ( a bound on the former is a bound on the operator norm, up to a constant). Is this the case, or am I barking up the wrong tree?

standard practice for large dense truncated svd computations?

2013-03-14T18:51:32Z

What are the standard methods of computing the rank-k truncated SVD of large dense matrices? My literature search yields results only for large sparse matrices.

I assume for k small that you use a Krylov subspace method (this is what Matlab's svds does). But (empirically) how large can k get before these methods become impractical, and then what should one resort to?

When is spectral norm of AB equal to that of BA?

2013-02-22T06:32:49Z

I have $A^{1/2} B A^{1/2} \preceq I$ for two PSD matrices $A$ and $B$, and I'd like to know if that implies $\|AB\|_2 \leq 1.$

The argument I was using to show this is that for any two square matrices $A$ and $B,$ it is always the case that $\|AB\|_2 = \|BA\|_2.$ I thought I read that this equality does hold in a reputable source, but I don't have access to it right now and I was unsuccessful in reproducing a proof.

I know the eigenvalues of $AB$ and $BA$ are the same modulo possibly having different numbers of zeros, so I'm worried that I might have ``remembered'' something that isn't true!

Any references/counterexamples for either question?

reference for perturbation of projection result

2012-07-06T17:45:51Z

I believe that this result is established by Golub and Zha in the course of their proof of Theorem 3.6 in "Perturbation Analysis of the Canonical Correlations of Matrix Pairs," but in a manner that's too messy to point to and say "here it is."

Unfortunately, this result also doesn't seem to follow readily from the results in Stewart's paper on perturbation theory for pseudoinverses and projections.

Is this result clearly established somewhere in the literature?

reference for this QR perturbation result?

2012-06-08T17:04:03Z

I believe this result is due to Stewart, but I haven't been able to track it down: let $A$ have full column rank and let $B = A + E$ where $P_{A} E = 0$. Then $$ \|(I - P_B)P_A\|^2_2 = 1 - \lambda_{\text{min}}(A(B^TB)^{-1} A^T) $$

Any idea where it's stated? And any extensions?

Answer by Alex Gittens for Does the minima of a sequence of convex convergent functions converge?

2012-05-11T21:47:10Z

No; here's a counterexample: let $f = 0$ and consider the minimizer $y = 0.$ Then you can construct convex functions which converge to $0$ pointwise but whose minima are always moving away from $y =0,$ e.g. $f_n(x) = (x - n)^2/n^n.$

Upper bounds on generalized Laguerre polynomials

2012-01-05T22:03:09Z

I evaluated an integral and obtained an expression with a Laguerre polynomial. I'd like something more explicit and useable.

Are there any known simple (e.g. exponential) upper bounds on the generalized Laguerre polynomials $L_{n}^{(\alpha)}(x)$?

So far I've only found some asymptotic expansions, but I'd like an actual upper bound.

is the kummer function monotonic decreasing in first argument?

2012-01-09T18:45:23Z

Let $b >0$ and $x<0.$ If $a_1 < a_2 < 0$ are integers then ${}_1F_1(a_2;b;x) < {}_1F_1(a_1;b;x).$ Is it true that in fact ${}_1F_1(a;b;x)$ is monotonic decreasing as a function of $a$?

is this bound on a kummer function known?

2012-01-06T02:06:20Z

Is it already known that ${}_1F_1(a;b;x) \leq \Gamma(b)(1+|x|)^{-a}$ when $a$ is an integer, $a <0,$ and $b>0?$ If it is, what is a reference?

my proof: Since the Kummer function can be written in terms of a generalized Laguerre polynomial, \begin{equation} \label{eqn:Kummer-Laguerre-equality} {}_1F_1(a;b;x) = \frac{\Gamma(1-a)\Gamma(b)}{\Gamma(b-a)} L_{-a}^{(b-1)}(x), \end{equation} when $a < 0,$ we proceed by bounding the generalized Laguerre polynomial on the right hand side.

Let $n = -a$ and $\alpha = b - 1.$ Then $$ L_{n}^{(\alpha)}(x) = \sum_{\ell=0}^n \frac{\Gamma(\alpha + n + 1)}{\Gamma(\alpha + \ell +1)(n-\ell)!\ell!} (-x)^\ell. $$ Our constraints on $a$ and $b$ ensure that each $\Gamma(\cdot)$ term in the above sum is positive. Furthermore, for $\ell=0,1,\ldots,n,$ $$ \Gamma(\alpha + \ell +1) \geq \Gamma(b) \geq \min_{x > 0} \Gamma(x) > 0.88. $$

It follows that $$ L_{n}^{(\alpha)}(x) \leq 1.14 \cdot \Gamma(\alpha + n + 1) \sum_{\ell =0}^n \frac{|x|^\ell}{(n-\ell)!\ell!} = 1.14 \cdot \Gamma(b-a) \frac{1}{(-a)!}(1 + |x|)^{-a}. $$ The last equality is a consequence of the binomial theorem.

The conclusion follows immediately when this estimate is used in the relation expressing ${}_1F_1$ in terms of the Laguerre polynomial.

density for Gaussian gram matrices

2011-12-04T01:32:54Z

Let $Z \sim \mathcal{N}(0,\Sigma \otimes I)$ (so the columns of $Z$ are distributed $\mathcal{N}(0, \Sigma)$) and $A = Z'Z.$ Is there a name for the distribution on $A$? Is the density known?

proofs of stochastic boundedness

2011-11-01T14:51:00Z

I'm looking at some statistical literature and trying to compare the results given there in probabilistic big-Oh notation with statements I'm more familiar with.

In particular, I'm trying to interpret statements of the form $$ \|\Sigma_{n(p)} - \Sigma \| = O_P\left( \frac{\log p}{n(p)}\right). $$ As far as i can tell from the rather terse wikipedia page on $o_p$ notation, this means that there is some constant $C$ that is independent of $p$ for which $$ \lim_{p \rightarrow \infty} \mathbb{P}\left( \|\Sigma_{n(p)} - \Sigma \| > C \frac{\log p}{n(p)}\right) = 0. $$

Is that correct?

Does this norm inequality hold for projections onto the range of a sum of matrices?

2011-05-02T18:59:37Z

Although it's simply stated, this is neither a homework problem or trivial (I think, but I'd be happy to be proven wrong :) ).

Let $A,B$ be matrices and $x$ be a vector. Is it true that $$ \|P_{A+B} x\| \geq \|P_A x\| - \|P_B x\|, $$ where $P_A$ is the projection onto the range space of $A$? (or is it true if you square the norms?)

I'm having difficulty even figuring out how to attack this: every attempt I've made falters on the facts that the range space of $A + B$ is not simply related to those of $A$ and $B$ and that the projection is nonlinear. Random instances haven't yet provided counterexamples to the inequality.

Why is the dimension of Gaussian variables is bounded by the dimension of the space?

2011-02-09T23:24:19Z

I'm looking at a probabilistic proof of a local version of Dvoretzky's theorem in Pisier's manuscript "Probabilistic Methods in the Geometry of Banach Spaces."

For each $\epsilon >0$ there is a number $\eta^\prime(\epsilon) > 0$ with the following property. Let $X$ be a Gaussian r.v. with values in a Banach space $B$ of dimension $N.$ Then $B$ contains a subspace $F$ of dimension $n = [\eta^\prime(\epsilon) d(X)]$ which is $(1+\epsilon)$-isomorphic to $\ell^n_2.$ Conversely, if $B$ contains a subspace $F$ with $F \stackrel{1+\epsilon}{\sim} \ell^n_2,$ then there is a $B$-valued Gaussian r.v. $X$ such that $d(X) \geq (1+\epsilon)^{-2}n.$

This statement uses the "dimension" $d(X)$ of a Gaussian variable, $$ d(X) = \mathbb{E}\|X\|^2/\sigma(X)^2, $$ where $$ \sigma(X)^2 = \sup \{ \mathbb{E} \xi(X)^2 \mid \|\xi\|_{B^\star} \leq 1 \} $$ is the weak variance of $X.$

For this to match the usual $n = O(\log N)$ statement of the theorem, you'd need a lower bound on $d(X)$ of order $\log N,$ and as a sanity check an upper bound of $O(N).$

Any hints or references on how to show these two bounds on $d(X)$? Pisier states that the upper bound $d(X) \leq N$ is easy to show, but I've not been able to prove even that.

Radstrom cancellation only for two convex sets?

2009-12-15T03:05:45Z

I've seen this statement of Radstrom cancellation: if $A +C \subset B+C$ where $A,B$ are convex, $B$ is closed, and $C$ is bounded, then $A \subset B.$

Is it essential that $A$ be convex?

characterization of continuous functionals in weak-star topology

2010-02-17T23:43:00Z

Reading Wojtaszczyk's Banach spaces for analysts, I'm trying to understand his proof that the space of all continuous linear functionals on $(X^\star,\sigma(X^\star, X))$ is $X$.

To show the $ \subseteq$ part, he says let $\varphi$ be any linear functional on $X^\star$ continuous in $\sigma(X^\star, X)$. Then $\{x^\star \in X^\star : |\varphi(x^\star)| < 1\} \supset \{x^\star \in X^\star : |x_j(x^\star)| < \epsilon, j=1,\ldots,n\}$ for some $\epsilon >0$ and some $x_1, \ldots, x_n \in X$. (Isn't this just saying since $\varphi^{-1}((-1,1))$ is open, it contains a neighborhood of 0?)

Then--- this is where I get lost--- he says that the result follows from the fact that if $\varphi_0, \ldots, \varphi_n$ are linear forms on a linear space $X$ (without any topology), then $\varphi_0 \in \text{span}\{\varphi_j\}_{j=1}^n$ iff $\text{ker}\varphi_0 \supset \cap_{j=1}^n \text{ker} \varphi_j$.

How is this fact relevant?

for a natural exponential family, A is the cumulant function of h?

2009-12-18T03:11:49Z

Reading "Monte Carlo Statistical Methods" by Robert and Casella, they mention that if $f(x) = h(x) \exp(\langle \theta, x \rangle - A(\theta))$ defines a family of distributions for $X$, parametrized by $\theta$, then $A$ is the cumulant generating function of $h(X)$. It seems like this should be easy to prove if it's true, but I don't see how to proceed. Any ideas/references?

Answer by Alex Gittens for Radstrom cancellation only for two convex sets?

2009-12-16T07:07:04Z

Hmm, I have an idea for a proof which works even when $A$ isn't convex:

$A \not\subset B$ iff there is a $a \in A$ and vector $x$ such that $\langle a, x\rangle >0$ and $\langle b, x \rangle \leq 0$ for all $b \in B$ (since $B$ is a closed convex set). Let $b \in B$ and $c \in C$ maximize $\langle b + c, x \rangle$, then $\langle a + c, x \rangle > \langle b + c, x \rangle$, so there is a point in $A + C$ that isn't in $B+C$.

This implies that if $A \not\subset B$ then $A + C \not\subset B+C$. Of course, there aren't really $b,c$ which maximize that quantity above, but I believe you could make this rigorous using approximation arguments.

Comment by Alex Gittens

2013-02-24T02:32:37Z

It's not clear at all that Gauss should be attributed credit for this formula, much less that he came up with it as a kid: see e.g. americanscientist.org/issues/pub/… It's such a simple (but neat) observation that it'd be problematic to attribute it to any one person--- I wouldn't be surprised if mathematicians as far back as Pythagoras knew this. After all, the pythagorean theorem is much less obvious.

Comment by Alex Gittens

2012-06-13T15:57:22Z

$P_A$ is the projection onto the range space of $A.$

Comment by Alex Gittens

2012-02-05T07:33:41Z

Thanks for the suggestions. I found a satisfactory bound by using very elementary estimates on the polynomial expression for $L_n^(\alpha).$ It's something like $L_n^(\alpha) \leq 1.14 \Gamma(\alpha +n + 1)(1+ |x|)^n$ ... this is probably incorrect in all but general form, since I'm changing notation and indexing on the fly here. At any rate, it turned out that the result I wanted can be gotten at without messing around with Laguerre polynomials.

Comment by Alex Gittens

2012-01-07T00:49:40Z

Not sure what you meant by context, but I provided a proof.

Comment by Alex Gittens

2012-01-06T23:57:58Z

Thanks for pointing that out. I revisited my proof: the rhs of the inequality needs to be divided by the minimum value of the gamma function over the positive real axis, about 0.88. This seems to fix the issue you highlighted.

Comment by Alex Gittens

2011-12-05T22:28:52Z

$Z$ is a matrix whose columns are distributed $\mathcal{N}(0, \Sigma).$ If the rows were distributed that way, then $Z'Z$ would be a Wishart distribution.

Comment by Alex Gittens

2011-11-03T14:19:06Z

Thanks for the reference. I think I'll also work through a couple of the proofs because I'm interested to see whether they prove their results by getting explicit tail bounds that hold for finite p (and then just state the theorem in a weaker way because of convention) or by using arguments that only hold asymptotically.

Comment by Alex Gittens

2011-02-11T02:58:53Z

Thanks! I'll check out the mentioned references.

Comment by Alex Gittens

2010-02-19T06:59:23Z

Thanks. I'll tell him :)