Motivated by the settings where sensing the entire tensor is infeasible, this paper proposes a novel tensor compressed sensing model, where measurements are only obtained from sensing each lateral slice via mutually independent matrices. Leveraging the low tubal rank structure, we reparameterize the unknown tensor ?* 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 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 Alt-PGD-Min achieves ϵ-accuracy recovery with ?(?²log1/?) iteration complexity and ?(?⁶rn₃logn₃(?²r(n₁+n₂)+n₁log1/ε)) sample complexity, where ? denotes tensor condition number of ?*. To further accelerate the convergence, especially when the tensor is ill-conditioned with large ?, we prove Alt-ScalePGD-Min that preconditions the gradient update using an approximate Hessian that can be computed efficiently. We show that Alt-ScalePGD-Min achieves ? independent iteration complexity ?(log1/ε) and improves the sample complexity to ?(?⁴rn₃log n₃(?⁴ r(n₁ + n₂)+n₁log 1/ε)). Experiments validate the effectiveness of the proposed methods.

In this paper, we propose a novel tube-wise local tensor compressed sensing (CS) model, where sensing operators are independently applied to each tube of a third-order tensor. To recover the low-rank ground truth tensor, we minimize a non-convex objective via Burer–Monteiro factorization and solve it using gradient descent with spectral initialization. We prove that this approach achieves exact recovery with a linear convergence rate. Notably, our method attains provably lower sample complexity than existing TCS methods. Our proof leverages the leave-one-out technique to show that gradient descent generates iterates implicitly biased towards solutions with bounded incoherence, which ensures contraction of optimization error in consecutive iterates. Empirical results validate the effectiveness of GD in solving the proposed local TCS model.

We consider learning a sparse model from linear measurements taken by a network of agents. Different from existing decentralized methods designed based on the LASSO regression with explicit $\ell_1$ norm regularization, we exploit the implicit regularization of decentralized optimization method applied to an over-parameterized nonconvex least squares formulation without penalization. Our first result shows that despite nonconvexity, if the network connectivity is good, the well-known decentralized gradient descent algorithm (DGD) with small initialization and early stopping can compute the statistically optimal solution. Sufficient conditions on the initialization scale, choice of step size, network connectivity, and stopping time are further provided to achieve convergence. Our result recovers the convergence rate of gradient descent in the centralized setting, showing its tightness. Based on the analysis of DGD, we further propose a communication-efficient version, termed T-DGD, by truncating the iterates before transmission. In the high signal-to-noise ratio (SNR) regime, we show that T-DGD achieves comparable statistical accuracy to DGD, while the communication cost is logarithmic in the number of parameters. Numerical results are provided to validate the effectiveness of DGD and T-DGD for sparse learning through implicit regularization.

High-dimensional image representation is a challenging task since data has the intrinsic low-dimensional and shift-invariant characteristics. Currently, popular methods, such as tensor-Singular Value Decomposition (t-SVD), have limited ability in expressing shift-invariant subspace knowledge underlying data. To these problem, we propose a high-dimensional image representation framework based on Tensor Convolution-like Low-Rank Dictionary (TCLRD), which considers the shift-invariant low-dimensional structure of a tensor-valued data by convolution-like low-rank dictionary learning and coefficient coding, to promote the high-dimensional image representation ability. To be specific, we first define the TCLRD framework with low-rank constraint for dictionary and coefficient, in which tensor factorization and tensor-tensor product over frequency domain can be understood as convolution-like operation when describing shift-invariant. Then, the tensor Schatten-p norm is introduced to verify that TCLRD has rational mathematical interpretation. We study the TCLRD minimization problem in tensor completion with the ADMM-based optimization algorithm. The efficient solving scheme with TCLRD is extendable to various low-rank models like tensor robust principal component analysis and subspace clustering, and prove their theoretical guarantees based on generalization error. Extensive experimental results demonstrate the proposed TCLRD methods are beyond state-of-the-arts in typical tasks, including image denoising, HSI completion and image clustering.

Low-rank tensor completion (LRTC) has shown promise in processing incomplete visual data, yet it often overlooks the inherent local smooth structures in images and videos. Recent advances in LRTC, integrating total variation regularization to capitalize on the local smoothness, have yielded notable improvements. Nonetheless, these methods are limited to exploiting local smoothness within the original data space, neglecting the latent factor space of tensors. More seriously, there is a lack of theoretical backing for the role of local smoothness in enhancing recovery performance. In response, this paper introduces an innovative tensor completion model that concurrently leverages the global low-rank structure of the original tensor and the local smooth structure of its factor tensors. Our objective is to learn a low-rank tensor that decomposes into two factor tensors, each exhibiting sufficient local smoothness. We propose an efficient alternating direction method of multipliers to optimize our model. Further, we establish generalization error bounds for smooth factor-based tensor completion methods across various decomposition frameworks. These bounds are significantly tighter than existing baselines. We conduct extensive inpainting experiments on color images, multispectral images, and videos, which demonstrate the efficacy and superiority of our method. Additionally, our approach shows a low sensitivity to hyper-parameter settings, enhancing its convenience and reliability for practical applications.

The tensor nuclear norm (TNN), defined as the sum of nuclear norms of frontal slices of the tensor in a frequency domain, has been found useful in solving low-rank tensor recovery problems. Existing TNN-based methods use either fixed or data-independent transformations, which may not be the optimal choices for the given tensors. As the consequence, these methods cannot exploit the potential low-rank structure of tensor data adaptively. In this article, we propose a framework called self-adaptive learnable transform (SALT) to learn a transformation matrix from the given tensor. Specifically, SALT aims to learn a lossless transformation that induces a lower average-rank tensor, where the Schatten- p quasi-norm is used as the rank proxy. Then, because SALT is less sensitive to the orientation, we generalize SALT to other dimensions of tensor (SALTS), namely, learning three self-adaptive transformation matrices simultaneously from given tensor. SALTS is able to adaptively exploit the potential low-rank structures in all directions. We provide a unified optimization framework based on alternating direction multiplier method for SALTS model and theoretically prove the weak convergence property of the proposed algorithm. Experimental results in hyperspectral image (HSI), color video, magnetic resonance imaging (MRI), and COIL-20 datasets show that SALTS is much more accurate in tensor completion than existing methods. The demo code can be found at https://faculty.uestc.edu.cn/gaobin/zh_CN/lwcg/153392/list/index.htm.

From the sparsity of vector to the sparsity of singular values, which essentially characterizes the low rank property of matrix. The sparsity measure based model is of significant interest in a range of contemporary applications in data analysis. However, there are different measurement strategies for sparse characterization of high dimensional tensor data. Albeit, most of the existing sparsity measures only consider the number of non-zero factor components, but ignore the geometric position distribution structure of non-zero elements in high-dimensional space. In this paper, based on the fact that sliced sparse distribution of the core tensor, a novel high order structure sparsity measure is proposed. More specifically, the sparsity measure unifies Tucker and CP tensor decomposition into a framework for general tensor. The CP decomposition of the core tensor with factor group sparse constraint realizes modeling the global low CP rank and the sliced sparse distribution of the non-zeros elements of the core tensor simultaneously. We apply minimizing high order structure sparse measurement to multispectral image denoising and deduce Alternating Direction Method of Multipliers (ADMM) optimization method to solve the model effectively. The subsequent experimental results show that the proposed algorithm is competitive with state-of-the art denoising methods.1