User alex gittens - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T05:40:06Z http://mathoverflow.net/feeds/user/2586 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/128544/relationship-between-numerical-and-spectral-radii-for-product-of-positive-definit relationship between numerical and spectral radii for product of positive definite matrices? Alex Gittens 2013-04-23T21:42:37Z 2013-04-24T01:01:00Z <p>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.$</p> <p>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.$ </p> <p>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?</p> http://mathoverflow.net/questions/124552/standard-practice-for-large-dense-truncated-svd-computations standard practice for large dense truncated svd computations? Alex Gittens 2013-03-14T18:51:32Z 2013-03-14T18:51:32Z <p>What are the standard methods of computing the rank-k truncated SVD of large dense matrices? My literature search yields results only for large <em>sparse</em> matrices.</p> <p>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?</p> http://mathoverflow.net/questions/122610/when-is-spectral-norm-of-ab-equal-to-that-of-ba When is spectral norm of AB equal to that of BA? Alex Gittens 2013-02-22T06:32:49Z 2013-02-22T18:51:06Z <p>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.$ </p> <p>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. </p> <p>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!</p> <p>Any references/counterexamples for either question?</p> http://mathoverflow.net/questions/101520/reference-for-perturbation-of-projection-result reference for perturbation of projection result Alex Gittens 2012-07-06T17:45:51Z 2012-07-07T19:37:35Z <p>Let $A$ and $B$ have the same rank and dimensions. If $P_A$ denotes the projection onto the range space of $A$, then $$\|P_A - P_B\|_2 \leq \|A - B\| \cdot \min (\|A^\dagger\|_2, \|B^\dagger\|_2).$$ Here $A^\dagger$ denotes the pseudoinverse of a matrix.</p> <p>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."</p> <p>Unfortunately, this result also doesn't seem to follow readily from the results in Stewart's paper on perturbation theory for pseudoinverses and projections. </p> <p>Is this result clearly established somewhere in the literature?</p> http://mathoverflow.net/questions/99135/reference-for-this-qr-perturbation-result reference for this QR perturbation result? Alex Gittens 2012-06-08T17:04:03Z 2012-06-08T17:04:03Z <p>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)$$</p> <p>Any idea where it's stated? And any extensions?</p> http://mathoverflow.net/questions/96711/does-the-minima-of-a-sequence-of-convex-convergent-functions-converge/96716#96716 Answer by Alex Gittens for Does the minima of a sequence of convex convergent functions converge? Alex Gittens 2012-05-11T21:47:10Z 2012-05-11T21:47:10Z <p>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.$ </p> http://mathoverflow.net/questions/85005/upper-bounds-on-generalized-laguerre-polynomials Upper bounds on generalized Laguerre polynomials Alex Gittens 2012-01-05T22:03:09Z 2012-02-04T12:13:58Z <p>I evaluated an integral and obtained an expression with a Laguerre polynomial. I'd like something more explicit and useable.</p> <p>Are there any known simple (e.g. exponential) upper bounds on the generalized Laguerre polynomials $L_{n}^{(\alpha)}(x)$? </p> <p>So far I've only found some asymptotic expansions, but I'd like an actual upper bound.</p> http://mathoverflow.net/questions/85275/is-the-kummer-function-monotonic-decreasing-in-first-argument is the kummer function monotonic decreasing in first argument? Alex Gittens 2012-01-09T18:45:23Z 2012-01-09T18:45:23Z <p>Let $b >0$ and $x&lt;0.$ If $a_1 &lt; a_2 &lt; 0$ are integers then ${}_1F_1(a_2;b;x) &lt; {}_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$?</p> http://mathoverflow.net/questions/85023/is-this-bound-on-a-kummer-function-known is this bound on a kummer function known? Alex Gittens 2012-01-06T02:06:20Z 2012-01-07T00:48:49Z <p>Is it already known that ${}_1F_1(a;b;x) \leq \Gamma(b)(1+|x|)^{-a}$ when $a$ is an integer, $a &lt;0,$ and $b>0?$ If it is, what is a reference? </p> <p>my proof: Since the Kummer function can be written in terms of a generalized Laguerre polynomial, $$\label{eqn:Kummer-Laguerre-equality} {}_1F_1(a;b;x) = \frac{\Gamma(1-a)\Gamma(b)}{\Gamma(b-a)} L_{-a}^{(b-1)}(x),$$ when $a &lt; 0,$ we proceed by bounding the generalized Laguerre polynomial on the right hand side.</p> <p>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.$$</p> <p>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.</p> <p>The conclusion follows immediately when this estimate is used in the relation expressing ${}_1F_1$ in terms of the Laguerre polynomial.</p> http://mathoverflow.net/questions/82591/density-for-gaussian-gram-matrices density for Gaussian gram matrices Alex Gittens 2011-12-04T01:32:54Z 2011-12-04T01:32:54Z <p>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? </p> http://mathoverflow.net/questions/79719/proofs-of-stochastic-boundedness proofs of stochastic boundedness Alex Gittens 2011-11-01T14:51:00Z 2011-11-01T22:53:48Z <p>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.</p> <p>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.$$</p> <p>Is that correct?</p> http://mathoverflow.net/questions/63724/does-this-norm-inequality-hold-for-projections-onto-the-range-of-a-sum-of-matrice Does this norm inequality hold for projections onto the range of a sum of matrices? Alex Gittens 2011-05-02T18:59:37Z 2011-05-02T20:47:09Z <p>Although it's simply stated, this is neither a homework problem or trivial (I think, but I'd be happy to be proven wrong :) ).</p> <p>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?)</p> <p>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.</p> http://mathoverflow.net/questions/54954/why-is-the-dimension-of-gaussian-variables-is-bounded-by-the-dimension-of-the-spa Why is the dimension of Gaussian variables is bounded by the dimension of the space? Alex Gittens 2011-02-09T23:24:19Z 2011-02-10T11:12:53Z <p>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."</p> <blockquote> <p>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.$</p> </blockquote> <p>This statement uses the "dimension" $d(X)$ of a Gaussian variable, $$d(X) = \mathbb{E}\|X\|^2/\sigma(X)^2,$$ where <code>$$\sigma(X)^2 = \sup \{ \mathbb{E} \xi(X)^2 \mid \|\xi\|_{B^\star} \leq 1 \}$$</code> is the weak variance of $X.$</p> <p>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).$</p> <p>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. </p> http://mathoverflow.net/questions/8944/radstrom-cancellation-only-for-two-convex-sets Radstrom cancellation only for two convex sets? Alex Gittens 2009-12-15T03:05:45Z 2010-09-16T03:36:27Z <p>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.$</p> <p>Is it essential that $A$ be convex? </p> http://mathoverflow.net/questions/15643/characterization-of-continuous-functionals-in-weak-star-topology characterization of continuous functionals in weak-star topology Alex Gittens 2010-02-17T23:43:00Z 2010-02-18T00:21:14Z <p>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$.</p> <p>To show the $\subseteq$ part, he says let $\varphi$ be any linear functional on $X^\star$ continuous in $\sigma(X^\star, X)$. Then <code>$\{x^\star \in X^\star : |\varphi(x^\star)| &lt; 1\} \supset \{x^\star \in X^\star : |x_j(x^\star)| &lt; \epsilon, j=1,\ldots,n\}$</code> 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?)</p> <p>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 <code>$\varphi_0 \in \text{span}\{\varphi_j\}_{j=1}^n$</code> iff $\text{ker}\varphi_0 \supset \cap_{j=1}^n \text{ker} \varphi_j$.</p> <p>How is this fact relevant?</p> http://mathoverflow.net/questions/9234/for-a-natural-exponential-family-a-is-the-cumulant-function-of-h for a natural exponential family, A is the cumulant function of h? Alex Gittens 2009-12-18T03:11:49Z 2009-12-18T03:50:50Z <p>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?</p> http://mathoverflow.net/questions/8944/radstrom-cancellation-only-for-two-convex-sets/9087#9087 Answer by Alex Gittens for Radstrom cancellation only for two convex sets? Alex Gittens 2009-12-16T07:07:04Z 2009-12-16T07:07:04Z <p>Hmm, I have an idea for a proof which works even when $A$ isn't convex:</p> <p>$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$.</p> <p>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.</p> http://mathoverflow.net/questions/122772/who-came-up-with-n-n1-2/122774#122774 Comment by Alex Gittens Alex Gittens 2013-02-24T02:32:37Z 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. <a href="http://www.americanscientist.org/issues/pub/gausss-day-of-reckoning/2" rel="nofollow">americanscientist.org/issues/pub/&hellip;</a> 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. http://mathoverflow.net/questions/99135/reference-for-this-qr-perturbation-result Comment by Alex Gittens Alex Gittens 2012-06-13T15:57:22Z 2012-06-13T15:57:22Z $P_A$ is the projection onto the range space of $A.$ http://mathoverflow.net/questions/85005/upper-bounds-on-generalized-laguerre-polynomials/87521#87521 Comment by Alex Gittens Alex Gittens 2012-02-05T07:33:41Z 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. http://mathoverflow.net/questions/85023/is-this-bound-on-a-kummer-function-known Comment by Alex Gittens Alex Gittens 2012-01-07T00:49:40Z 2012-01-07T00:49:40Z Not sure what you meant by context, but I provided a proof. http://mathoverflow.net/questions/85023/is-this-bound-on-a-kummer-function-known/85047#85047 Comment by Alex Gittens Alex Gittens 2012-01-06T23:57:58Z 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. http://mathoverflow.net/questions/82591/density-for-gaussian-gram-matrices Comment by Alex Gittens Alex Gittens 2011-12-05T22:28:52Z 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. http://mathoverflow.net/questions/79719/proofs-of-stochastic-boundedness/79738#79738 Comment by Alex Gittens Alex Gittens 2011-11-03T14:19:06Z 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. http://mathoverflow.net/questions/54954/why-is-the-dimension-of-gaussian-variables-is-bounded-by-the-dimension-of-the-spa/55017#55017 Comment by Alex Gittens Alex Gittens 2011-02-11T02:58:53Z 2011-02-11T02:58:53Z Thanks! I'll check out the mentioned references. http://mathoverflow.net/questions/15643/characterization-of-continuous-functionals-in-weak-star-topology/15649#15649 Comment by Alex Gittens Alex Gittens 2010-02-19T06:59:23Z 2010-02-19T06:59:23Z Thanks. I'll tell him :)