Abstract. 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 [Formula: see text]-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.

A plethora of previous studies indicates that making full use of multifarious intrinsic properties of primordial data is a valid pathway to recover original images from their degraded observations. Typically, both low-rankness and local-smoothness broadly exist in real-world tensor data such as hyperspectral images and videos. Modeling based on both properties has received a great deal of attention, whereas most studies concentrate on experimental performance, and theoretical investigations are still lacking. In this paper, we study the tensor compressive sensing problem based on the tensor correlated total variation, which is a new regularizer used to simultaneously capture both properties existing in the same dataset. The new regularizer has the outstanding advantage of not using a trade-off parameter to balance the two properties. The obtained theories provide a robust recovery guarantee, where the error bound shows that our model certainly benefits from both properties in ground-truth data adaptively. Moreover, based on the ADMM update procedure, we design an algorithm with a global convergence guarantee to solve this model. At last, we carry out experiments to apply our model to hyperspectral image and video restoration problems. The experimental results show that our method is prominently better than many other competing ones. Our code and Supplementary Material are available at https://github.com/fsliuxl/cs-tctv.

We consider Quantized Tensor Robust Principal Component Analysis (Q-TRPCA), which aims to recover a low-rank tensor and a sparse tensor from noisy, quantized, and sparsely corrupted measurements. A nonconvex constrained maximum likelihood (ML) estimation method is proposed for Q-TRPCA. We provide an upper bound on the Frobenius norm of tensor estimation error under this method. Making use of tools in information theory, we derive a theoretical lower bound on the best achievable estimation error from unquantized measurements. Compared with the lower bound, the upper bound on the estimation error is nearly order-optimal. We further develop an efficient convex ML estimation scheme for Q-TRPCA based on the tensor nuclear norm (TNN) constraint. This method is more robust to sparse noises than the latter nonconvex ML estimation approach. Conducting experiments on both synthetic data and real-world data, we show the effectiveness of the proposed methods.

Low-rank tensor recovery (LRTR) is a natural extension of low-rank matrix recovery (LRMR) to high-dimensional arrays, which aims to reconstruct an underlying tensor from incomplete linear measurements M(X). However, LRTR ignores the error caused by quantization, limiting its application when the quantization is low-level. In this work, we take into account the impact of extreme quantization and suppose the quantizer degrades into a comparator that only acquires the signs of M(X). We still hope to recover X from these binary measurements. Under the tensor Singular Value Decomposition (t-SVD) framework, two recovery methods are proposedthe first is a tensor hard singular tube thresholding method; the second is a constrained tensor nuclear norm minimization method. These methods can recover a real n1 n2 n3 tensor X with tubal rank r from m random Gaussian binary measurements with errors decaying at a polynomial speed of the oversampling factor := m/((n1+ n2)n3r). To improve the convergence rate, we develop a new quantization scheme under which the convergence rate can be accelerated to an exponential function of . Numerical experiments verify our results, and the applications to real-world data demonstrate the promising performance of the proposed methods.

Recovering low-rank matrices by nuclear norm minimization and local-smooth matrices by total variation seminorm minimization are two common methods in the context of compressive sensing. As a matter of fact, the two properties simultaneously exist in many real-world datasets, typically exampling hyperspectral images. The two methods may not perform well in this situation. To better address this issue, in this letter, we study the correlated total variation norm minimization problem both theoretically and numerically. We obtain an error bound for the robust recovery of our method in theory, which reflects that this model indeed benefits from low-rank and local-smooth properties of the matrix to be restored. Experiments on the recovery of hyperspectral images show that this model is superior to many other competing ones.

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 X ∈ ℝn1×n2×n3can be approximated from Ω((n1+ n2)n3r) random Gaussian measurements. In addition, incorporating nonadaptive thresholds in the measurements, it is proved that the full 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 λ := m/(n1+ n2)n3r, i.e., O(λ-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 λ. Numerical experiments are conducted to demonstrate our results.

This letter considers the recovery of a low-tubal-rank tensor from incomplete linear observations. It is shown that the unknown tensor Z ∈ Rn1×n2×n3of tubal-rank r can be reconstructed as a unique solution of a tractable method - tensor nuclear norm (TNN) minimization, provided that the number of Gaussian observations m ≥ 3r(n1+ n2- r)n3+ 1. In this work, we examine the fundamental question of the minimal number of linear observations needed to reconstruct the tensor Z from these observations, regardless of the practicality of the reconstruction scheme. Consequently, we provide two benchmark results so that different reconstruction schemes including TNN minimization can be compared to each other. Specifically, we conclude that m ≥ 2r(n1+ n2- 2r)n3and m ≥ r(n1+ n2- r)n3+ 1 Gaussian observations are necessary and sufficient to guarantee uniform recovery and nonuniform recovery using tensor tubalrank minimization method, respectively.