1
$\begingroup$

In the document Trapdoors for Lattices, section 5.4 Gaussian Sampling, they introduce the parameter $\sqrt{\Sigma_{\bf G}}$, which is related to the lattice $\Lambda^\perp(\bf G)$. They use it as a bound for the smoothing parameter of this lattice, therefore $\sqrt{\Sigma_{\bf G}}\in\mathbb{R}$. But later on, they do some calculation as if it were a matrx when they write $s_1(\sqrt{\Sigma_{\bf G}})$, where $s_1(\cdot)$ is the first singular value of the argument.

If this is not confusing enough, in 2.1 they use the $\Sigma$ notation extensively to refer to matrices. Even when defining the root of a matrix

I feel like there is a small detail I'm missing, so if anyone could help me understand what's going on here that'd be great.

$\endgroup$

1 Answer 1

0
$\begingroup$

While I haven't verified this, I think a more natural interpretation of this is that $\sqrt{\Sigma_{\mathbf{G}}}$ is simply the matrix square root (in the sense of the Cholesky decomposition) of the positive semidefinite $\Sigma_{\mathbf{G}}$. Your main concern seems to be the bound $$\sqrt{\Sigma_{\mathbf{G}}} \geq \eta_\epsilon(\Lambda^\perp(\mathbf{G})).$$ While it is natural to think this is an inequality between real numbers (and therefore $\Sigma_{\mathbf{G}}$ should be real, which would be confusing), there is another interpretation. Namely, one can write this (perhaps less ambiguously) as

$$\sqrt{\Sigma_{\mathbf{G}}} \succeq \eta_\epsilon(\Lambda^\perp(\mathbf{G}))\cdot I,$$ where $\succeq$ is the inequality in the the Loewner order on matrices, and $I$ is an appropriately-sized identity matrix.

This interpretation is consistent with the paper's (claimed) chosen notation. I quote from the first pagagraph of section 2

or convenience, we sometimes use a scalar $s$ to refer to the scaled identity matrix $sI$, where the dimension will be clear from context.

For the notation selected for the Loewner order, I quote the 4th paragraph of Section 2.1

A symmetric matrix $\Sigma\in\mathbb{R}^{n\times n}$ is positive definite (respectively, positive semidefinite), written $\Sigma > 0$ (resp., $\Sigma\geq 0$), if $x^t\Sigma x > 0$ (resp., $x^t\Sigma x \geq 0$) for all nonzero $x \in\mathbb{R}^n$. We have $\Sigma > 0$ if and only if $\Sigma$ is invertible and $\Sigma^{-1} > 0$, and $\Sigma \geq 0$ if and only if $\Sigma^+ \geq 0$. Positive (semi)definiteness defines a partial ordering on symmetric matrices: we say that $\Sigma_1 > \Sigma_2$ if $(\Sigma_1 − \Sigma_2) > 0$, and similarly for $\Sigma_1 \geq \Sigma_2$ ...

In general though, this is the natural interpretation solely because $\sqrt{\Sigma_{\mathbf{G}}}$ is mentioned as the parameter of a Gaussian. This should be a strong hint you are in the multi-dimensional setting (and this is the Cholesky decomposition of a covariance matrix, which is always positive-semidefinite, i.e. the Cholesky decomposition always exists). This is because in 1 dimensions it is horrible notation --- one would simplify $\sqrt{\sigma^2} = \sigma$ to get a much simpler expression in terms of more familiar parameters. While overloading $\geq$ and writing $s$ rather than $sI$ is somewhat ambiguous, it is much less of a notational crime than writing $\sqrt{\Sigma_{\mathbf{G}}}$ for $\sigma$, so is the natural interpretation.

$\endgroup$
1
  • $\begingroup$ Well that makes a lot of sense, thanks! I knew there was something fishy :) $\endgroup$ Jun 27, 2023 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.