  This paper proposes a set of piecewise Toeplitz matrices as the linear
mapping/sensing operator $\mathcal{A}: \mathbf{R}^{n_1 \times n_2} \rightarrow
\mathbf{R}^M$ for recovering low rank matrices from few measurements. We prove
that such operators efficiently encode the information so there exists a unique
reconstruction matrix under mild assumptions. This work provides a significant
extension of the compressed sensing and rank minimization theory, and it
achieves a tradeoff between reducing the memory required for storing the
sampling operator from $\mathcal{O}(n_1n_2M)$ to $\mathcal{O}(\max(n_1,n_2)M)$
but at the expense of increasing the number of measurements by $r$. Simulation
results show that the proposed operator can recover low rank matrices
efficiently with a reconstruction performance close to the cases of using
random unstructured operators.
