Random Matrix Lecture 05

[[lecture-data]]

Info

let current = dv.current();
let previous = current.previous_lecture;
 
// get notes with this as the previous
let pages = dv.pages("")
	.where(p => p.previous_lecture)
	.where(p => String(p.previous_lecture)
		.includes(dv.current().file.link))
 
let output = `:LiArrowBigLeftDash: ${previous || "No Previous Lecture"} | `;
 
if (pages.length > 0) {
	output += pages
		.map(p => p.file.link).join(", ");
} else {
	output += 'No Next Lecture'
}
 
output += ' :LiArrowBigRightDash:'
 
dv.el('div', output)

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 {\mathbb{R}}^{d\times m}$. The goal of compressed sensing is to recover $x\in {\mathbb{R}}^m$ from measurement(s) / observation(s) $y=Gx\in {\mathbb{R}}^d$.

• $y_i={\sum }_{j=1}^m{G}_{ij}{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 {\mathbb{R}}^m$?

Answer

In general, we need $G$ to be injective (ie, $d\ge 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$?

$x$ to be sparse.

We want

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 basis (that we choose). ie, there is some 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 $GA\tilde{x}=Gx$.
• 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

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

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

2. 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\ne 0\}=|\{i:x_i\ne 0\}|$ If $||x|{|}_0\le 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^{\prime }|{|}_0\le k,Gx=G{x}^{\prime }⟹x=x^{\prime }$ ie $G$ is injective on $\{x:||x|{|}_0\le k\}\subset {\mathbb{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\ll m$.

$k$-nullspace property

$G$ has the $k$-nullspace property (NSP) if for all $||x|{|}_0\le k$, $x\ne 0,Gx\ne 0$

see nullspace property

Proposition

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

Proof

$(⟸)$ (via contrapositive) Suppose $G$ does not distinguish $k$-sparse vectors. Then there is some $x\ne x^{\prime }$ with $||x|{|}_0,||x^{\prime }|{|}_0\le k$ such that $Gx=G{x}^{\prime }$. Note that $||x-x^{\prime }|{|}_0\le 2k$, but $Gx-G{x}^{\prime }=G(x-x^{\prime })\ne 0$ Thus $G$ does not have the $2k$ NSP.

$(⟹)$ Now, suppose $G$ does distinguish $k$ sparse vectors. Suppose $||x|{|}_0\le 2k$ and $x\ne 0$. Then there exist $x^{\prime },x^{\prime \prime }$ $k$-sparse such that $x=x^{\prime }-x^{\prime \prime }$. Then $0\ne G{x}^{\prime }-G{x}^{\prime \prime }=G(x^{\prime }-x^{\prime \prime })=Gx$ ie $G$ has the $2k$ NSP.

\tag*{$\blacksquare$}

see distinguishing is equivalent to double nullspace property

$(k,\delta )$ restricted isometry property

$G$ has the $(k,\delta )$ restricted isometry property (RIP) if for all $x\ne 0$ with $||x|{|}_0\le k$ we have $(1-\delta )||x|{|}^2\le ||Gx|{|}^2\le (1+\delta )||x|{|}^2$

see restricted isometry property

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

Theorem

If $G$ has $(k,\delta )$ RIP with $\delta <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=Gx⟹y=Gx+\epsilon$

2.5.2 Random Sensing Matrices

Theorem

Suppose $k\ge 1$ and $\delta \in (0,1)$ and $d\ge 64\frac{k\log m}{{\delta }^2}$. Let $G\sim \mathcal{N}{\left(0,\frac{1}{d}\right)}^{\otimes d\times m}$. Then $\mathbb{P}[G\text{ has }(k,\delta )\text{-RIP}]\ge 1-\frac{2}{m^k}$

(We want to reduce the number of measurements required)

Proof

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

1. $x^{(S)}\in {\mathbb{R}}^k$ as the restriction to indices in $S$

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

If $||x|{|}_0\le k$ and all non-zero indices are in $S$, ie $\text{supp}(x)\subset S$, then we have $Gx=G^{(S)}{x}^{(S)}\text{ and }||x||=||x^{(S)}||$ In this case, the $(k,\delta )$ RIP is equivalent to requiring that (for all $S\subset [m]$ with $|S|=k$) we have $(1-\delta )||x^{(S)}|{|}^2\le ||G^{(S)}{x}^{(S)}|{|}^2\le (1+\delta )||x^{(S)}|{|}^2$ Now, let ${\hat{x}}^{(S)}:=\frac{x^{(S)}}{||x^{(S)}||}$. Then

\iff-\delta &\leq \hat{x}^{(S)}(G^{(S)T}G^{(S)} - I_{k})\hat{x}^{(S)} \leq \delta \\ \iff \lvert \lvert G^{(S)T}G^{(S)} -I_{k}\rvert \rvert &\leq\delta \end{align}$$

So, applying the union bound, we can see

\mathbb{P}[G \text{ not }(k,\delta)\text{-RIP}] &\leq_{\text{UB}} \sum_{S \subseteq[m], \lvert S \rvert =k} \mathbb{P}[\lvert \lvert G^{(S)T} G^{(S)} - I+k \rvert \rvert > \delta] \end{align}$$ Now, $\text{Law}(G^{(S)}) ={\cal N}\left( 0, \frac{1}{d} \right)^{\otimes d\times m}$. So introduce $H \sim {\cal N}(0, 1)^{\otimes k \times d}$. Then we have $$\begin{align} \mathbb{P}[G \text{ not }(k,\delta)\text{-RIP}] &\leq {{m}\choose{k}} \mathbb{P}[\lvert \lvert HH^T - dI_{k} \rvert \rvert >\delta d] \\ (*)&\leq {m\choose{k}} \cdot 2 \exp\left( -\frac{1}{8}\min \left\{ \frac{\delta^2d^2}{4d}, \frac{\delta d}{2} \right\} \right) \end{align}$$ Where we get $(*)$ from the [[high probability bound for operator norm of difference for Gaussian covariance matrix]] we saw [[Random Matrix Lecture 04#non-constructive-existence-of-nets|last time]]. And continuing the calculation, we see $$\begin{align} \mathbb{P}[G \text{ not }(k,\delta)\text{-RIP}] &\leq m^k \cdot 2 \exp\left( -\frac{\delta^2}{32}d \right) \\ &=2\exp\left( k\log m-\frac{\delta^2}{32}d \right) \\ &\leq 2\exp(-k\log m) \\ &= \frac{2}{m^k} \end{align}$$ $$\tag*{$\blacksquare$}$$

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

Summary

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

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

---

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

$G=U\Sigma V^T={\sum }_1^d{\sigma }_i{u}_i{v}_i^T$ $u_i(G),v_i(G)$ with ${\sigma }_d\le \cdots \le {\sigma }_1$

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

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

Review

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 basis (that we choose). ie, there is some 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 $GA\tilde{x}=Gx$.
• 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 clean ⏳ 2025-09-12 ❌ 2025-12-08
  • 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>
}