Random Matrix Lecture 05

[[lecture-data]]

[!info]

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)

Class Notes

Pages 27-30

Important

HW 1 posted online
project topics to be chosen w hw 2
This week only: office hours Wednesday at 3pm

2. Rectangular Matrices

Geometric method later, not at all, or in the notes

2.5 Application: Compressed Sensing

eigenvalues for Gaussian random matrices

Let $G \in R^{d \times m}$ . The goal of compressed sensing is to recover $x \in R^{m}$ from measurement(s) / observation(s) $y = G x \in R^{d}$ .

$y_{i} = \sum_{j = 1}^{m} G_{i j} x_{j}$ some linear projection/measurement of the vector $x$

Example

Medical imaging (eg, MRI). In this case, we get to choose $G$ .

Question

How many measurements ( $d$ ) are needed to recover $x \in R^{m}$ ?

Answer

In general, we need $G$ to be injective (ie, $d \geq m$ ).

BUT if $x$ has some sort of structure, then compressed sensing wants to make $d$ much smaller.

Question

What kind of structure do we need for $x$ ?

Answer

We want $x$ to be sparse.

Remark

Note that knowing that I can design $G$ (called the sensing matrix) to recover sparse $x$ is equivalent to knowing that there is a basis $A$ in which $x$ is sparse (thus, WLOG, we assume is sparse)

Demonstration

Assume that $x$ is sparse is some known invertible $A$ such that $x = A \tilde{x}$ is sparse. (it is important that $A$ is known as it encodes our prior assumptions about $x$ )
Then we have $G A \tilde{x} = G x$ .
Assuming I have designed my $G$ to recover (sparse) $x$ , I can then recover $\tilde{x} = A^{- 1} x$

Suppose I have some $G$ that recovers sparse $x$ . Then I can also recover $\tilde{x}$ that is sparse in basis $A$ .

2.5.1 Null Space and Restricted Isometry Properties

Question

When does $G x$ uniquely determine $x$ for $x$ sparse? (when is $G$ injective?)

This is an existence question: is there a reverse mapping?

How do we actually recover $x$ (quickly)?

This is an algorithm question: what algorithm do we want?
Not on topic for this class / we will not discuss

Sparsity

We denote the sparsity of a vector $x$ by

| | x | |_{0} := # {i : x_{i} \neq 0} = | {i : x_{i} \neq 0} |

If $| | x | |_{0} \leq k$ , we say that $x$ is $k$ -sparse

Note

This is not a [[norm]]; it is not homogeneous.

see [[sparsity]]

Distinguishes

k

-sparse vectors

$G$ distinguishes $k$ -sparse vectors if

| | x | |_{0}, | | x^{'} | |_{0} \leq k, G x = G x^{'} ⟹ x = x^{'}

ie $G$ is injective on ${x : | | x | |_{0} \leq k} \subset R^{n}$ .

see [[distinguishes sparse vectors]]

If such a $G$ exists, then yes, a way to recover $x$ exists! Now, we want to find for a $d ≪ m$ .

k

-nullspace property

$G$ has the $k$ -nullspace property (NSP) if for all $| | x | |_{0} \leq k$ ,

x \neq 0, G x \neq 0

see [[nullspace property]]

Proposition

$G$ distinguishes $k$ -sparse if and only if $G$ has the $2 k$ -NSP

Proof

(⟸)

(via contrapositive)

Suppose $G$ does not distinguish $k$ -sparse vectors. Then there is some $x \neq x^{'}$ with $| | x | |_{0}, | | x^{'} | |_{0} \leq k$ such that $G x = G x^{'}$ . Note that $| | x - x^{'} | |_{0} \leq 2 k$ , but

G x - G x^{'} = G (x - x^{'}) \neq 0 $ $ T h u s $ G $ d o e s * n o t * h a v e t h e $ 2 k $ N S P .

(⟹)

Now, suppose $G$ does distinguish $k$ sparse vectors. Suppose $| | x | |_{0} \leq 2 k$ and $x \neq 0$ . Then there exist $x^{'}, x^{″}$ $k$ -sparse such that $x = x^{'} - x^{″}$ . Then

0 \neq G x^{'} - G x^{″} = G (x^{'} - x^{″}) = G x

ie $G$ has the $2 k$ NSP.

\begin{matrix} ◼ \end{matrix}

see [[distinguishing is equivalent to double nullspace property]]

(k, δ)

restricted isometry property

$G$ has the $(k, δ)$ restricted isometry property (RIP) if for all $x \neq 0$ with $| | x | |_{0} \leq k$ we have

(1-\delta)\lvert \lvert x \rvert \rvert {#2} \leq \lvert \lvert Gx \rvert \rvert {#2} \leq (1+\delta) \lvert \lvert x \rvert \rvert {#2}

see [[restricted isometry property]]

Restricted to sparse vectors, $G$ is approximately an isometry.

Theorem

If $G$ has $(k, δ)$ RIP with $δ < 1$ , then $G$ has $k$ NSP

This follows immediately from the definition.

See [[restricted isometry implies nullspace property]]

Note

The RIP is more useful than the NSP for algorithms, especially when noise is added to $y = G x ⟹ y = G x + ε$

2.5.2 Random Sensing Matrices

Theorem

Suppose $k \geq 1$ and $δ \in (0, 1)$ and $d \geq 64 \frac{k \log m}{δ^{2}}$ . Let $G \sim N {(0, \frac{1}{d})}^{\otimes d \times m}$ . Then

P [G has (k, δ) -RIP] \geq 1 - \frac{2}{m^{k}}

(We want to reduce the number of measurements required)

Proof

Suppose $S \subset [m], | S | = k$ and $x \in R^{m}$ . Define

$x^{(S)} \in R^{k}$ as the restriction to indices in $S$
$G^{(S)} \in R^{d \times k}$ be the restriction to columns with indices in $S$

If $| | x | |_{0} \leq k$ and all non-zero indices are in $S$ , ie $supp (x) \subset S$ , then we have
$G x = G^{(S)} x^{(S)} and | | x | | = | | x^{(S)} | |$
In this case, the $(k, δ)$ RIP is equivalent to requiring that
(for all $S \subset [m]$ with $| S | = k$ ) we have
$(1-\delta)\lvert \lvert x^{(S)} \rvert \rvert {#2} \leq \lvert \lvert G^{(S)}x^{(S)} \rvert \rvert {#2} \leq (1+\delta) \lvert \lvert x^{(S)} \rvert \rvert {#2}$

Now, let ${\hat{x}}^{(S)} := \frac{x^{(S)}}{| | x^{(S)} | |}$ . Then
$\begin{aligned} ⟺ - δ & \leq {\hat{x}}^{(S)} (G^{(S) T} G^{(S)} - I_{k}) {\hat{x}}^{(S)} \leq δ \\ ⟺ | | G^{(S) T} G^{(S)} - I_{k} | | & \leq δ \end{aligned}$

So, applying the union bound, we can see
$\begin{aligned} P [G not (k, δ) -RIP] & \leq_{UB} \sum_{S \subseteq [m], | S | = k} P [| | G^{(S) T} G^{(S)} - I + k | | > δ] \end{aligned}$
Now, $Law (G^{(S)}) = N {(0, \frac{1}{d})}^{\otimes d \times m}$ . So introduce $H \sim N (0, 1)^{\otimes k \times d}$ . Then we have
$\begin{aligned} P [G not (k, δ) -RIP] & \leq (\binom{m}{k}) P [| | H H^{T} - d I_{k} | | > δ d] \\ (*) & \leq (\binom{m}{k}) \cdot 2 \exp (- \frac{1}{8} min {\frac{δ^{2} d^{2}}{4 d}, \frac{δ d}{2}}) \end{aligned}$
Where we get $(*)$ from the last time. And continuing the calculation, we see
$\begin{aligned} P [G not (k, δ) -RIP] & \leq m^{k} \cdot 2 \exp (- \frac{δ^{2}}{32} d) \\ = 2 \exp (k \log m - \frac{δ^{2}}{32} d) \\ \leq 2 \exp (- k \log m) \\ = \frac{2}{m^{k}} \end{aligned}$ $\begin{matrix} ◼ \end{matrix}$

see [[dimension requirements for gaussian random matrix to be a restricted isometry with high probability]]

Summary

To recover $x \in R^{m}$ (information theoretically)

in general, we need $d \geq m$
if $x$ is $k$ sparse, $d \geq k \log m$

Next Time:
Singular Vectors of $G \sim N (0, 1)^{\otimes d \times m}$ ([[singular value decomposition]])

G = U Σ V^{T} = \sum_{1}^{d} σ_{i} u_{i} v_{i}^{T}

$u_{i} (G), v_{i} (G)$ with $σ_{d} \leq \dots \leq σ_{1}$

Only well-defined (up to sign) if the singular values are distinct

Theorem
The singular values of $G$ are almost surely distinct.

Review

#flashcards/math/rmt

Remark

Note that knowing that I can design $G$ (called the sensing matrix) to recover sparse $x$ is equivalent to {1||knowing that I can do so and that there is a basis $A$ in which $x$ is sparse} (thus, WLOG, we assume $x$ is {1||sparse})

Demonstration

Assume that $x$ is sparse is some known invertible $A$ such that $x = A \tilde{x}$ is sparse. (it is important that $A$ is known as it encodes our prior assumptions about $x$ )
Then we have $G A \tilde{x} = G x$ .
Assuming I have designed my $G$ to recover (sparse) $x$ , I can then recover $\tilde{x} = A^{- 1} x$

TODO

Finish cleaning ⏳ 2025-09-10 ✅ 2025-09-10
Finish linking ⏳ 2025-09-10 ✅ 2025-09-10
finish adding flashcards #class_notes/clean ⏳ 2025-09-12
- Flashcards up to RIP so far (non inclusive)

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>
}