7
$\begingroup$

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.

$\endgroup$
4
+50
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Yesid Fonseca V. May 24 at 15:36
  • $\begingroup$ @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$. $\endgroup$ – Alex Ravsky May 24 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.