Suppose that $N$ is an $\epsilon$-net (where $\epsilon$ is a small absolute constant) on the unit sphere $S^{n-1}$ in $\mathbb{R}^n$, and $T$ is an $n\times n$ matrix such that $\|Tx\|_2\geq 1$ for all $x\in N$.

Is it true that $\|T\|_\ast \geq cn$ for some (small) constant $c$ (which could depend on $\epsilon$? Here $\|T\|_\ast$ means the trace norm of $T$, that is, $\|T\|_\ast = \sigma_1(T) + \cdots + \sigma_n(T)$, where $\sigma_i(T)$ are the singular values of $T$.

My guess is not. One can choose $T$ be have a big constant singular value and all the rest singular values are tiny (like $1/n$), and the net completely evades the orthogonal complement to the vector associated with the largest singular value. Is it so?

What if $T$ satisfies a further constraint that $\|T\|_F\geq\sqrt{n}$ (where $\|T\|_F$ is the Frobenius norm of $T$), will we have $\|T\|_\ast\geq cn$ in this case?

  • $\begingroup$ What if T is the identity matrix? $\endgroup$ – Anthony Quas Jan 5 '17 at 2:02
  • $\begingroup$ Could you please explicitly define $\Vert T \Vert$? $\endgroup$ – Pat Devlin Jan 5 '17 at 2:12
  • $\begingroup$ @PatDevlin yes, i've modified the post. $\|T\|_1$ is the trace norm / nuclear norm of $T$. $\endgroup$ – user58955 Jan 5 '17 at 5:02
  • $\begingroup$ The nuclear norm is usually denoted by $\| \cdot \|_*$. $\endgroup$ – Rodrigo de Azevedo Jan 5 '17 at 13:37
  • 3
    $\begingroup$ As you say, if $T$ is the matrix with a single non-zero entry of $1/\epsilon$ in the top left coordinate, and $S$ is the collection of all points with $x$ coordinate at least $\epsilon$, then $S$ is a $2\epsilon$ net satisfying your condition, but $\|T\|_*$=1/\epsilon$. $\endgroup$ – Anthony Quas Jan 5 '17 at 17:50

Your Answer

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

Browse other questions tagged or ask your own question.