2
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ What if T is the identity matrix? $\endgroup$
    – Anthony Quas
    Jan 5, 2017 at 2:02
  • $\begingroup$ Could you please explicitly define $\Vert T \Vert$? $\endgroup$
    – Pat Devlin
    Jan 5, 2017 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, 2017 at 5:02
  • $\begingroup$ The nuclear norm is usually denoted by $\| \cdot \|_*$. $\endgroup$
    – Rodrigo de Azevedo
    Jan 5, 2017 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, 2017 at 17:50

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.