I have this confusion related to the convexity and tractability of a problem.
The given problem is
maximize $u^TSu$ subject to $||u||_2 = 1$ and card(u) <= r
This is a NP hard problem because of the combinatorial nature of the cardinality.
Then they say they relax it to a convex form like
maximize Tr(SU)
subject to Tr(U) =1 , Rank(U) = 1, $Card(U) <= r^2$ and U>=0
I didn't get the tractability of the second problem there is still $Card(U) <= r^2$. So how is it tractable?