# Existence of the $\Omega$ set in "Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization"

In the proof of Lemma 4.3 in [1], they claim the following:

Let $$U$$ be a subspace of $$\mathbb{R}^{m\times n}$$ with dim$$(U)=d$$ and let $$\delta>0$$. Then, there exists a set $$\Omega\subset\mathbb{R}^{m\times n}$$ wiht at most $$(12/\delta)^d$$ elements such that for every $$X\in U$$ with $$\lVert X\rVert_F\leq 1$$ there exists a $$Q\in\Omega$$ such that $$\lVert X-Q\rVert_F \leq \delta/4$$.

I don't see the reason why this is true.

References

[1] Recht, B., Fazel, M., & Parrilo, P. A. (2010). Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3), 471-501.

I know the following proof. The space $$U$$ endowed with the Frobenius_norm is isometric to a Euclidean space $$\Bbb R^d$$ and $$V=\{X\in U: \|X\|_F\le 1\}$$, that is $$V$$ is a unit ball of a $$U$$. Given a number $$\varepsilon>0$$, a subset $$\Theta$$ of $$V$$ is $$\varepsilon$$-separated, if $$\|Q-Q'\|_F\ge\varepsilon$$ for each distinct $$Q,Q’\in\Theta$$. Let $$\Omega$$ be a maximal $$\delta/4$$-separated subset of $$V$$. Then for each $$X\in V$$ there exists $$Q\in\Omega$$ such that $$\lVert X-Q\rVert_F \leq \delta/4$$. On the other hand, for each $$Q\in\Omega$$ let $$B(Q)\subset U$$ be an open ball of radius $$\delta/8$$ centered at $$Q$$. Then for each distinct $$Q,Q’\in\Omega$$, balls $$B(Q)$$ and $$B(Q’)$$ are disjoint and are contained in an open ball $$B$$ of radius $$1+\delta/8$$ centered at zero. Comparing the $$d$$-dimensional volumes of $$B$$ and $$B(Q)$$ for $$Q\in\Omega$$, wee see that
$$|\Omega|(\delta/8)^d\le (1/2+\delta/8)^d,$$
that is $$|\Omega|\le \left(1+\frac 4{\delta}\right)^d$$.
So $$|\Omega|\le \left(\frac {12}{\delta}\right)^d$$ for $$\delta\le \tfrac 18$$.
• You said "The space $U$ endowed with the Frobenius_norm is isometric to a Euclidean space $\mathbb{R}^d$". Could you mention which is the explicit isomorphism? May 24, 2019 at 15:36
• @YesidFonsecaV. This fact is not so straightforward. The space $\Bbb R^{m\times n}$ endowed with the Frobenius norm is Euclidean, see the definition of the Frobenius norm. Thus each $d$-dimensional linear subspace $U$ of $\Bbb R^{m\times n}$ is isometric to a $d$-dimensional Euclidean space of $\Bbb R^{m\times n}$, that is to $\Bbb R^d$. May 24, 2019 at 16:27