1
$\begingroup$

Let X be a given matrix of dimension $p \times q$. Let $G$ be a $s \times p$ dimensional matrix of standard normal/Gaussian random variables.

  • Are there cases where one can been able to quantify $P_G [ \vert \vert \vert X \vert \vert - \vert \vert GX \vert \vert \vert > t ] $ ?

(choose any matrix norm for which something like this can be shown!)

In the above I am trying to quantify how much some matrix norm deviates under doing such a projection. I am thinking of this as doing a compression of the row size from $p$ to $s << p$.

  • Are there other ways known of doing such a compression on the rows preserving some norm of the matrix?
Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

That's a trivial simplification of the Johnson-Lindenstrauss lemma . The matrix $X$ can be seen as a set of $q$ points in $p$ dimensions. Let us first prove the following result, than your question will follow directly with a union bound: (by the way, I'm going to assume that your matrix $G$ is normalized)

Theorem Let $x \in \mathbb{R}^p$ and assume that the entries of the matrix $\tilde{G} \in \mathbb{R}^{s \times p}$ are drawn at random from a Gaussian distribution. Let $G = \frac{1}{\sqrt{s}}\tilde{G}$. Then $$ \mathbb{P}\left( |\|Gx\|_2^2 - \|x\|_2^2| \leq \varepsilon \|x\|_2^2 \right) \geq 1-2e^{-(\varepsilon^2-\varepsilon^3)s/4} $$

The proof uses a small lemma about the $\chi^2$ distribution which can be proved via Markov's inequality, after applying an exponential.

Proof First of all, remember that $\mathbb{E}[\|Gx\|_2^2] = \|x\|_2^2$. It is also worth mentioning that the individual components of the image vector $(Gx)_j/\|x\|_2$ for $1 \leq j \leq s$ are independent Normal variable with variance $1/\sqrt{s}$. As a consequence $\|Gx\|_2^2/\|x\|_2^2$ behaves as a $\chi^2/s$ random variable with $s$ degrees of freedom. Thus it follows, using classical results on the $\chi^2$ distribution, that $$ \mathbb{P}\left(\|Gx\|_2^2 \geq (1+\varepsilon) \|x\|_2^2 \right) = \mathbb{P}(\sum_{j=1}^s \frac{(Gx)_j}{\|x\|_2} \geq 1 + \varepsilon) = \mathbb{P}(\frac{1}{s}\chi^2 \geq 1 + \varepsilon) = \mathbb{P}(\chi^2 \geq (1+\varepsilon)s) \leq e^{-(\varepsilon^2-\varepsilon^3)s/4}. $$ Similarly, the following bounds hold $$ \mathbb{P}\left(\|Gx\|_2^2 \leq (1-\varepsilon) \|x\|_2^2 \right) = \mathbb{P}(\chi^2 \leq (1-\varepsilon)s) \leq e^{-(\varepsilon^2-\varepsilon^3)s/4}. $$ Combining both bounds together yields the expected result.

The result you asked for can be obtained by considering the norm $\|X\|_2^2 = \sum_{j = 1}^s\|x_j\|_2^2$ and using a union bound, playing with the constants

EDIT: adding some information relative to the estimations with the $\chi^2$ random variables. Let $x_1,\cdots,x_s$ be independent random Gaussian variables. $P=\mathbb{P}(\chi_s^2\geq (1+\varepsilon)s) = \mathbb{P}(\sum_{i=1}^sx_i^2 \geq (1+\varepsilon)s) = \mathbb{P}(\operatorname{exp}\left(\lambda \sum_{i=1}^sx_i^2\right) \geq \operatorname{exp}\left(\lambda (1+\varepsilon)s \right))$.

From here, we have Markov's inequality which yields $$P\leq \frac{\mathbb{E}\left(\operatorname{exp}\left(\lambda \sum_{i=1}^sx_i^2\right)\right)}{ \operatorname{exp}\left(\lambda (1+\varepsilon)s \right)} = \frac{\left(\mathbb{E}\left(\operatorname{exp}\left(\lambda x_i^2\right)\right)\right)^s}{ \operatorname{exp}\left(\lambda (1+\varepsilon)s \right)} = \frac{\left(\frac{1}{1-2\lambda}\right)^{k/2}}{\operatorname{exp}\left(\lambda (1+\varepsilon)s \right)}.$$ This expression is true for all $\lambda$, and in particular for $\lambda = \varepsilon/(2(1+\varepsilon))$, which achieves the minimum. We then only use the fact that $1+\varepsilon \leq \operatorname{exp}(\varepsilon-(\varepsilon^2-\varepsilon^3)/2)$. The other bound is obtained in a similar way.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks! You want me to think of your $x$ as columns of my $X$? So you are choosing some particular matrix norm such that $\vert \vert G X \vert \vert$ can be related to the $q$ different $\vert \vert Gx\vert \vert_2$? (one $x$ for each column) And could you kindly make explicit as to what you mean by saying that $G$ is "normalized"? (I was merely thinking of it as $G_{ij} \sim {\cal N} (0,1)$) May be you can explicitly state the distribution from which the entries in $G$ are being drawn? $\endgroup$
    – Student
    Commented Jun 26, 2016 at 17:53
  • $\begingroup$ Indeed, $X = [x_1, \cdots, x_q]$, which means in particular that, with $\|X\|_2^2 = \sum_{j = 1}^q \|x_j\|_2^2$, you also have $\|GX\|_2^2 = \sum_{j=1}^q\|Gx_j\|_2^2$ (this is simple linear algebra) By normalization, I mean that you divided all the columns by the variance (i.e. actually use my $G$, which is a Gaussian matrix whose entries are divided by $\sqrt{s}$) . $\endgroup$
    – Jean-Luc Bouchot
    Commented Jun 26, 2016 at 18:30
  • $\begingroup$ So your $\tilde{G}_{ij}$ are not drawn from the ${\cal N}(0,1)$? So it seems that your argument is made for the Frobenius norm. Any ideas about how much of this carries on to other norms? (like say the $k-Ky-Fan$ norm?) $\endgroup$
    – Student
    Commented Jun 26, 2016 at 19:31
  • $\begingroup$ It seems a bit hard to trace this particular property of chi-squared distribution that you are quoting. A degree$-s$ chi-squared distribution has its pdf $\frac{ x^{ -1+\frac{s}{2}} e^{-x/2 }}{ 2^{ \frac{s}{2}}\Gamma( \frac{s}{2})}$. So if $Q$ is a random variable being sampled from a degree$-s$ chi-squared distribution then are you claiming that, $P_{Q \sim \chi^2(s)} [ Q \geq (1+\epsilon) ] = \int_{1+\epsilon}^\infty dx \frac{ x^{ -1+\frac{s}{2}} e^{-x/2 }}{ 2^{ \frac{s}{2}}\Gamma( \frac{s}{2})} \leq e^{ - \frac{(\epsilon^2 - \epsilon^3)s}{4}} $ ? $\endgroup$
    – Student
    Commented Jun 26, 2016 at 21:17
  • $\begingroup$ Let $x_1,\cdots,x_s$ be independent random Gaussian variables. $P=\mathbb{P}(\chi_s^2\geq (1+\varepsilon)s) = \mathbb{P}(\sum_{i=1}^sx_i^2 \geq (1+\varepsilon)s) = \mathbb{P}(\operatorname{exp}\left(\lambda \sum_{i=1}^sx_i^2\right) \geq \operatorname{exp}\left(\lambda (1+\varepsilon)s \right))$. From here, we have Markov's inequality which yields $$P\leq\mathbb{E}(\operatorname{exp}\left(\lambda \sum_{i=1}^sx_i^2\right))/ \operatorname{exp}\left(\lambda (1+\varepsilon)s \right)$$. And then we can optimize for $\lambda$. I'll edit my answer and add more details. $\endgroup$
    – Jean-Luc Bouchot
    Commented Jun 28, 2016 at 11:20
2
$\begingroup$

In general, you can apply a Gaussian concentration inequality for Lipschitz functions, see for example Proposition 4 below

https://terrytao.wordpress.com/2009/06/09/talagrands-concentration-inequality/

For special norms, you can obtain better results if you take advantage of the geometry of the corresponding norm.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You are thinking of the matrix norm as the relevant Lipschitz function here? And you have any comments about whether concentration for one norm (like as explained for the Frobenius in the above) automatically implies such a concentration for other norms? $\endgroup$
    – Student
    Commented Jun 27, 2016 at 14:21
  • $\begingroup$ Yes. For each norm and depending on its geometry, you will get a different Lipschitz constant which will appear on your bounds. For Frobenius norm, you have a Hilbert space, so you might be able to get tighter bounds with more elaborate arguments. $\endgroup$
    – zouzias
    Commented Jun 28, 2016 at 7:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .