Robust Tensor Completion from Uniformly Dithered One-Bit Observations

Recently, the problem of one-bit tensor completion (1BTC) has garnered increasing attention and has been extensively investigated both theoretically and experimentally. However, prior works heavily relied on the precise knowledge on the distribution of the dither (i.e., the noise prior to one-bit quantization), which is not applicable to applications that involve unknown prequantization noise. The main goal of this paper is to address this limitation and develop a 1BTC method robust to both noise and corruption. Within the framework of tensor SVD, we demonstrate the robustness by studying the following two settings: (i) 1BTC under sub-Gaussian noises, and (ii) a more challenging scenario where sparse corruptions (besides sub-Gaussian noise) also are present. Built upon a novel usage of an -loss function in 1BTC, we propose regularized Lasso for the first setting and a constrained Lasso for the second setting, and both recovery programs are accompanied by theoretical recovery guarantees. We establish nearly matching minimax lower bounds for both settings with unquantized observations, which demonstrates that our recovery methods are near-optimal and the proposed quantization scheme only induces minor information loss. Moreover, we propose optimization algorithms and conduct experiments on both synthetic and real-world data to validate our theory and the robustness of our method.