epsilon net restricted inner product bounds the operator norm

Evaluation Error: SyntaxError: Unexpected token '>'

at DataviewInlineApi.eval (plugin:dataview:19027:21)
at evalInContext (plugin:dataview:19028:7)
at asyncEvalInContext (plugin:dataview:19038:32)
at DataviewJSRenderer.render (plugin:dataview:19064:19)
at DataviewJSRenderer.onload (plugin:dataview:18606:14)
at DataviewJSRenderer.load (app://obsidian.md/app.js:1:1182416)
at DataviewApi.executeJs (plugin:dataview:19607:18)
at DataviewCompiler.eval (plugin:digitalgarden:10763:23)
at Generator.next (<anonymous>)
at fulfilled (plugin:digitalgarden:77:24)

Lemma

If $X$ is an epsilon net of $S^{d - 1}$ or $B^{d}$ , then

| | Δ | |_{X} \leq | | Δ | | \leq \frac{1}{1 - 2 ϵ} | | Δ | |_{X}

(if $ϵ \in (0, \frac{1}{2})$ for the second inequality)

Proof

The first inequality is immediate from the definition of the restricted inner product. So we prove only the second inequality:

Let $x \in S^{d - 1}$ be such that $| x^{T} Δ x | = | | Δ | |$ and let $x_{i} \in X$ such that $| | x - x_{i} | | \leq ϵ$ . Then

\begin{aligned} | | Δ | |_{X} & \geq | x_{i}^{T} Δ x_{i} | \\ = | (x + (x_{i} - x))^{T} Δ (x + (x_{i} - x)) | \\ = \underset{| | Δ | |}{\underset{⏟}{| x^{T} Δ x |}} - \underset{\leq | | x | | \cdot | | Δ | | \cdot | | x_{i} - x | | \leq ϵ | | Δ | |}{\underset{⏟}{| x^{T} Δ (x_{i} - x) |}} - \underset{\leq ϵ | | Δ | |}{\underset{⏟}{| (x_{i} - x)^{T} Δ x_{i} |}} \\ \geq (1 - 2 ϵ) | | Δ | | \end{aligned}

\begin{matrix} ◼ \end{matrix}

File	Last Modified
high probability bound for operator norm of difference for Gaussian covariance matrix	2025-09-04
Random Matrix Lecture 04	2025-09-09

File

Last Modified

high probability bound for operator norm of difference for Gaussian covariance matrix

2025-09-04

Random Matrix Lecture 04

2025-09-09

epsilon net restricted inner product bounds the operator norm

References

See Also

TODO

Mentions