Exercises

For $\alpha \neq 0$, $\|\alpha\mathbf{x}\|_0 = \|\mathbf{x}\|_0$. A norm requires $\|\alpha\mathbf{x}\| = |\alpha|\,\|\mathbf{x}\|$, which fails.

$\|\mathbf{x}\|_0=2$, $\|\mathbf{x}\|_1=7$, $\|\mathbf{x}\|_2=5$.

$-2, 0, 0, 0.5$.

$\mu=0.2$, so $s < \tfrac{1}{2}(1+5)=3$. Exact recovery is guaranteed for $s\leq 2$.

$\mu \geq \sqrt{90/(10\cdot 99)} = \sqrt{90/990}\approx 0.301$.

A vertex is an extreme point: a point that is not a convex combination of two others in the set. In the $\ell_1$-ball, these are $\pm\mathbf{e}_i$ for $i=1,\ldots,N$.

There are $2N$ such points, all $1$-sparse with $\|\pm\mathbf{e}_i\|_1 = 1$.

Any column of $I_M$ paired with any column of $\mathbf{H}/\sqrt{M}$ has inner product $1/\sqrt{M}$. Columns of $I_M$ are pairwise orthogonal; columns of $\mathbf{H}$ are pairwise orthogonal.

$\mu = 1/\sqrt{M}$, achieving the Welch bound for $N=2M$.

$\tfrac{1}{2}\|\mathbf{y}-\mathbf{A}\mathbf{x}\|_2^2$ is a convex quadratic in $\mathbf{x}$ (Hessian $\mathbf{A}^{H}\mathbf{A}\succeq 0$).

Every norm is convex by the triangle inequality.

Every local minimum is global. Descent algorithms converge to the global optimum. The dual is well-posed and the KKT conditions characterize optima. Convexity is why LASSO scales to millions of variables.

If $\mathbf{y}=\mathbf{A}\mathbf{x}=\mathbf{A}\mathbf{x}'$ with $\mathbf{x}\neq\mathbf{x}'$ both $s$-sparse, then $\mathbf{v}=\mathbf{x}-\mathbf{x}'$ is $2s$-sparse and $\mathbf{A}\mathbf{v}=0$.

RIP gives $\|\mathbf{A}\mathbf{v}\|_2^2 \geq (1-\delta_{2s})\|\mathbf{v}\|_2^2 > 0$, contradicting $\mathbf{A}\mathbf{v}=0$.

$\mathbf{0}\in -\mathbf{A}^{H}(\mathbf{y}-\mathbf{A}\hat{\mathbf{x}})+\lambda\,\partial\|\hat{\mathbf{x}}\|_1$.

For $i$ with $\hat{x}_i\neq 0$: $[\mathbf{A}^{H}(\mathbf{y}-\mathbf{A}\hat{\mathbf{x}})]_i = \lambda\,\mathrm{sign}(\hat{x}_i)$. For $i$ with $\hat{x}_i=0$: $|[\mathbf{A}^{H}(\mathbf{y}-\mathbf{A}\hat{\mathbf{x}})]_i| \leq \lambda$.

Inactive coordinates must have correlation with the residual bounded by $\lambda$.

With $C\approx 2$ (typical constant): $50 \geq 2s\log(500/s)$. Trying $s=5$: $2\cdot 5\cdot\log(100) \approx 46$. So $s\approx 5$ is feasible.

$s \lesssim 5$ likely recoverable; $s\gtrsim 10$ unlikely.

$\min_x \tfrac{1}{2}(x-v)^2 + \lambda|x|$. Subgradient condition: $x-v+\lambda\partial|x|\ni 0$.

If $v>\lambda$: $x=v-\lambda>0$. If $v<-\lambda$: $x=v+\lambda<0$. Else $x=0$. This is $\mathrm{soft}_{\lambda}(v)$.

Suppose distinct $s$-sparse $\mathbf{x},\mathbf{x}'$ give the same $\mathbf{y}$. Then $\mathbf{v}=\mathbf{x}-\mathbf{x}'$ is $2s$-sparse, nonzero, and $\mathbf{A}\mathbf{v}=0$, i.e.\ columns of $\mathbf{A}$ on $\mathrm{supp}(\mathbf{v})$ are dependent.

This contradicts $\mathrm{spark}(\mathbf{A}) > 2s$, so $\mathbf{x}=\mathbf{x}'$.

$\|\mathbf{A}^{H}\mathbf{A}\|_F^2=\sum_{i,j}|\langle\mathbf{A}_{i},\mathbf{A}_{j}\rangle|^2 = N + 2\sum_{i<j}|\langle\mathbf{A}_{i},\mathbf{A}_{j}\rangle|^2$.

Since $\mathbf{A}^{H}\mathbf{A}$ is $N\times N$ of rank $\leq M$, $\|\mathbf{A}^{H}\mathbf{A}\|_F^2\geq(\mathrm{tr}(\mathbf{A}^{H}\mathbf{A}))^2/M=N^2/M$.

$N + N(N-1)\mu^2 \geq N^2/M$ (bounding the average off-diagonal by $\mu^2$). Solving for $\mu$: $\mu^2\geq(N-M)/(M(N-1))$.

Let $\mathbf{h}=\hat{\mathbf{x}}-\mathbf{x}^\star$. Feasibility of both $\mathbf{x}^\star$ and $\hat{\mathbf{x}}$ gives $\|\mathbf{A}\mathbf{h}\|_2\leq 2\epsilon$. Optimality of $\hat{\mathbf{x}}$ gives $\|\mathbf{h}_{S^c}\|_1\leq\|\mathbf{h}_S\|_1$ where $S=\mathrm{supp}(\mathbf{x}^\star)$.

Let $S_1$ be the top-$s$ entries of $\mathbf{h}_{S^c}$, $S_2$ the next, etc. A standard bound gives $\sum_{j\geq 2}\|\mathbf{h}_{S_j}\|_2\leq\|\mathbf{h}_{S^c}\|_1/\sqrt{s}\leq\|\mathbf{h}_S\|_1/\sqrt{s}\leq\|\mathbf{h}_{S\cup S_1}\|_2$.

$(1-\delta_{2s})\|\mathbf{h}_{S\cup S_1}\|_2^2\leq\|\mathbf{A}\mathbf{h}_{S\cup S_1}\|_2^2\leq\|\mathbf{A}\mathbf{h}\|_2\cdot\|\mathbf{A}\mathbf{h}_{S\cup S_1}\|_2+\delta_{2s}\sqrt{2}\|\mathbf{h}_{S\cup S_1}\|_2^2$. The condition $\delta_{2s}<\sqrt{2}-1$ makes the coefficient positive; solving yields $\|\mathbf{h}\|_2\leq C\epsilon$.