We present a method for learning representations shared across multiple tasks. Multi-task learning has become increasingly important recently in applications such as collaborative filtering, object detection, integration of databases, signal processing etc. Our method addresses the problem of learning a low-dimensional subspace on which task regression vectors lie. This non-convex problem can be relaxed as a trace (nuclear) norm regularization problem, which we solve with an alternating minimization algorithm. This algorithmic scheme can be shown to always converge to an optimal solution. Moreover, the method can easily be extended in order to use nonlinear feature maps as inputs via reproducing kernels. This is a consequence of optimality conditions known as representer theorems, for which we show a necessary and sufficient condition. Finally, we consider matrix regularization with more general spectral functions, such as the Schatten Lp norms, instead of the trace norm. We show that our algorithm and results apply in these cases as well.