Low-Tubal-Rank Tensor Recovery From One-Bit Measurements

This paper focuses on the recovery of low-tubal-rank tensors from binary measurements under the frame of tensor Singular Value Decomposition. We show that the direction of a tubal-rank-$r$ tensor $\bm{\mathcal{X}}\in \R^{n_1\times n_2\times n_3}$ can be approximated from $\Omega((n_1+n_2)n_3r)$ random Gaussian measurements. In addition, incorporating nonadaptive thresholds in the measurements, it is proved that the full $\bm{\mathcal{X}}$ can be recovered. As we will see, under this nonadaptive measurement scheme, recovery errors decay at the rate of polynomial of the oversampling factor $\lambda:=m/(n_1+n_2)n_3r$, i.e., $\mathcal{O}(\lambda^{-1/6})$. In order to obtain faster decay rate, we introduce a recursive strategy which generates thresholds according to previous estimates for each iteration. Under this quantization scheme, An iterative recovery algorithm is proposed which establishes recovery errors decaying at the rate of exponent of $\lambda$. Numerical experiments are conducted to demonstrate our results.