epsilon net restricted inner product bounds the operator norm

[[concept]]

[!themes] Topics

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 eval (plugin:digitalgarden:90:61)

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}

Note

++++ interpretation of special $x$

References

const modules = await cJS()

const COLUMNS = [  
	{ id: "Name", value: page => page.$link },  
	{ id: "Last Modified", value: page => modules.dateTime.getLastMod(page) },
];  
  
return function View() {  
	const current = dc.useCurrentFile();
// Selecting `#game` pages, for example. 
	let queryString = `@page and linksto(${current.$link})`;
	let pages = dc.useQuery(queryString);
	
	// check types
	pages = pages.filter( (p) => !modules.typeCheck.checkAll(p, current) ).sort()
	
	
	return <dc.Table columns={COLUMNS} rows={pages} paging={20}/>;  
}

const { dateTime } = await cJS()

return function View() {
	const file = dc.useCurrentFile();
	return <p class="dv-modified">Created {dateTime.getCreated(file)}     ֍     Last Modified {dateTime.getLastMod(file)}</p>
}

epsilon net restricted inner product bounds the operator norm

References

See Also

TODO

Mentions