Motivated from the settings where sensing the entire tensor is infeasible, we consider a novel tensor compressed sensing model, where measurements are obtained from mutually independent matrix sensing for each lateral slice. More concretely, for a tensor ${\boldsymbol {\mathcal X}}^\star \in \mathbb{R}^{n1 \times n_2 \times n_3}$ with tubal rank $r \ll \min \{n_1,n_2,n_3\}$, we aim to recover it from $m$ independent linear operators of each of its $n_2$ lateral slices, i.e., from $\boldsymbol y{ji}:= \langle \boldsymbol{\mathcal A}_i(:,j,:), \boldsymbol{\mathcal X}^\star(:,i,:) \rangle, (i,j) \in n_2 \times m$, where $\boldsymbol{\mathcal X}^\star(:,i,:) \in \mathbb{R}^{n_1 \times n_3}$ denotes its $i$-th lateral slice and $ \boldsymbol{\mathcal A}_i(:,j,:)$ denotes $j$-th sensing matrix for $i$-th slice. Leveraging the low-rank structure, we reparameterize the unknown tensor ${\boldsymbol {\mathcal X}}^\star$ using two compact tensor factors and formulate the recovery problem as a nonconvex minimization problem. To solve the problem, we first propose an alternating minimization algorithm, termed $\textsf{Alt-PGD-Min}$, that iteratively optimizes the two factors using a projected gradient descent and an exact minimization step, respectively. Despite nonconvexity, we prove that $\textsf{Alt-PGD-Min}$ achieves $\epsilon$-accuracy recovery with $\mathcal O\left( \kappa^2 \log \frac{1}{\epsilon}\right)$ iteration complexity and $\mathcal O\left( \kappa^6rn_3\log n_3 \left( \kappa^2r\left(n_1 + n_2 \right) + n_1 \log \frac{1}{\epsilon}\right) \right)$ sample complexity, where $\kappa$ denotes tensor condition number of $\boldsymbol{\mathcal X}^\star$. To further accelerate the convergence, especially when the tensor is ill-conditioned with large $\kappa$, we further propose $\textsf{Alt-ScalePGD-Min}$ that preconditions the gradient update using an approximate Hessian that can be computed efficiently. We show that $\textsf{Alt-ScalePGD-Min}$ achieves $\kappa$ independent iteration complexity $\mathcal O(\log \frac{1}{\epsilon})$ and improves the sample complexity to $\mathcal O\left( \kappa^4 rn_3 \log n_3 \left( \kappa^4r(n_1+n_2) + n_1 \log \frac{1}{\epsilon}\right) \right)$. Experiments validate the effectiveness of the proposed methods.