I would like to calculate
$$\min_{\tau} ||J_1 \tau_1 + \cdots + J_p \tau_p + D ||_*$$
where $\tau_1, \dots, \tau_p \in \mathbb{R}$, $J_1, \dots, J_p, D \in \mathbb{R}^{m \times n}$ and $\|\cdot\|_*$ is sum of its singular values. Since $m$ and $n$ can be up to some hundred, the $O(n^6)$ interior-point method is definitely too slow for me.
Here's a perfect reference (PDF): "Interior-point method for nuclear norm approximation with application to system identification". One approach would be to convert the problem to a semidefinite program $$\begin{array}{ll} \text{minimize} & \frac{1}{2}\left(\mathop{\textrm{Tr}}(W_1)+\mathop{\textrm{Tr}}(W_2)\right) \\ \text{subject to} & \begin{bmatrix} W_1 & J_1 \tau_1 + \cdots + J_p \tau_p + D \\ \left( J_1 \tau_1 + \cdots + J_p \tau_p + D \right)^T & W_2 \end{bmatrix} \succeq 0 \end{array}$$ and solve this using one of the many semidefinite programming solvers available. But as this paper shows, a custom solver will often be more efficient, particularly if $m\ll n$ or $m\gg n$.