Some Schatten norm stuff
Recall the Schatten p-norm of a matrix 
: 
where 
are the singular values of . They’re interesting, among other reasons, because they’re unitarily invariant. Schatten and Von Neumann came up with these while investigating matrix analogues of the finite 
spaces— they’re the norms of the vectors of singular values.
Show that 
, where 
is the modulus of the matrix.
Note that the Schatten 2-norm (aka Frobenius norm aka Hilbert-Schmidt norm) can be easily calculated 
, and is actually induced by the inner product 
. When is positive, show that 
is also easily calculable: 
.
Can you show that Schatten 
-norms have the dual norms you’d expect from analogy with the usual norms? It’s fun 
Can you think of any other interesting properties of the Schatten norms?
Possibly relevant posts:
- Equivalence of the
norm and the 
norm (1/27/2010) - Trace dual of the
norm (1/19/2010) - Max-min property and an application (2/9/2010)
A very interesting question, which I don’t think has been answered, and which I really would like to know the answer to, is how to efficiently calculate the trace/nuclear norm of a non-symmetric matrix.
For a general matrix, the naive method is to find the singular values, an O(n^3) calculation. But for a symmetric matrix, you just use the trace, an O(n) calculation. It’s such a huge discrepancy!
Anyone with suggestions? Ideally, there’d be an algorithm in less than O(n^3) [e.g. O(n) or O(n log(n)) preferably], but as a consolation would be an algorithm that’s still O(n^3) but with smaller constants and more stable than a SVD decomposition.
Or is beating O(n^3) theoretically impossible?