Abstract In low-rank & sparse matrix decomposition, the entries of the sparse part are often assumed to be i.i.d. sampled from a random distribution. But the structure of sparse part, as the central interest of many problems, has been rarely studied. One motivating problem is tracking multiple sparse object flows (motions) in video. We introduce “shifted subspaces tracking (SST)” to segment the motions and recover their trajectories by exploring the low-rank property of background and the shifted subspace property of each motion. SST is composed of two steps, background modeling and flow tracking. In step 1, we propose “semi-soft GoDec” to separate all the motions from the low-rank background L as a sparse outlier S. Its soft-thresholding in updating S significantly speeds up GoDec and facilitates the parameter tuning. In step 2, we update X as S obtained in step 1 and develop “SST algorithm” Pk further decomposing X as X = i=1 L(i)?? (i)+ S+G, wherein L(i) is a low-rank matrix storing the ith flow after transformation ? (i). SST algorithm solves k sub-problems in sequel by alternating minimization, each of which recovers one L(i) and its ? (i) by randomized method. Sparsity of L(i) and between-frame affinity are leveraged to save computations. We justify the effectiveness of SST on surveillance video sequences.