Tong Wu

Tensor low-rank representation (TLRR) is effective for tensor recovery, but existing methods are mainly restricted to third-order tensors. This paper studies robust recovery of order-d (d ≥ 4) tensors from sparse corruptions. We first propose high-order tensor low-rank representation (HTLRR), which operates directly on order-d tensors under the tensor singular value decomposition (t-SVD) algebraic framework and avoids reshaping, thereby preserving intrinsic multilinear structure. Under mild conditions, we prove that HTLRR can exactly recover the underlying clean tensor. For the noisy case, we further establish a stable recovery result showing that the reconstruction errors are bounded by the noise level. We then introduce high-order latent tensor low-rank representation (HLTLRR), which augments the representation with latent tensor samples to better handle settings with insufficient observed samples. Extensive experiments on 4D, 5D, and 6D visual denoising tasks demonstrate that HTLRR and HLTLRR consistently outperform existing baselines, with HLTLRR showing stronger robustness in challenging settings.

Tensors, which give a faithful and effective representation to deliver the intrinsic structure of multi-dimensional data, play a crucial role in an increasing number of signal processing and machine learning problems. However, tensor data are often accompanied by arbitrary signal corruptions, including missing entries and sparse noise. A fundamental challenge is to reliably extract the meaningful information from corrupted tensor data in a statistically and computationally efficient manner. This paper develops a scaled gradient descent (ScaledGD) algorithm to directly estimate the tensor factors with tailored spectral initializations under the tensor-tensor product (t-product) and tensor singular value decomposition (t-SVD) framework. With tailored variants for tensor robust principal component analysis, (robust) tensor completion and tensor regression, we theoretically show that ScaledGD achieves linear convergence at a constant rate that is independent of the condition number of the ground truth low-rank tensor, while maintaining the low per-iteration cost of gradient descent. To the best of our knowledge, ScaledGD is the first algorithm that provably has such properties for low-rank tensor estimation with the t-SVD. Finally, numerical examples are provided to demonstrate the efficacy of ScaledGD in accelerating the convergence rate of ill-conditioned low-rank tensor estimation in a number of applications.

Recently, low-rank tensor analysis has received widespread attention, due to its effectiveness in many applications in computer vision and pattern recognition. However, existing methods mainly focus on recovering tensor data contaminated by Gaussian or gross sparse noise, which leads to unsatisfactory results when handling outliers or sample-specific corruptions. In this regard, this paper proposes an outlier-robust tensor low-rank representation (OR-TLRR) method that can perform outlier detection and clustering of two-dimensional data simultaneously based on the t-SVD framework. In particular, for tensor observations with arbitrary outlier corruptions, OR-TLRR has provable performance guarantees for exactly recovering the row space of clean data and detecting outliers under mild conditions. This paper also introduces a divide-and-conquer algorithm that can substantially accelerate OR-TLRR without performance drop, while maintaining OR-TLRR’s strong recovery guarantees. Furthermore, it extends OR-TLRR to the case when parts of the data are missing. Finally, it reports the outcomes of a series of numerical experiments involving both synthetic and real data that demonstrate the superiority of the proposed algorithms over existing approaches in the literature.

This work studies the low-rank high-order tensor completion (HOTC) problem, which aims to exactly recover a low-rank order-d (d ≥ 4) tensor from partially observed entries. Leveraging the low-rank structure under the tensor Singular Value Decomposition (t-SVD) decomposition, instead of relying on the computationally expensive tensor nuclear norm (TNN), we propose an efficient algorithm, termed the HOTC-SGD, that directly estimates the high-order tensor factors—starting from a spectral initialization—via scaled gradient descent (SGD). Theoretically, we rigorously establish the recovery guarantee of HOTC-SGD under mild assumptions, demonstrating that it achieves linear convergence to the true low-rank tensor at a constant rate that is independent of the condition number. Numerical experiments on both synthetic and real-world data verify our results and demonstrate the superiority of our method.

The advent of ubiquitous multidimensional arrays poses unique challenges for low-rank modeling of tensor data due to higher-order relationships, gross noise, and large dimensions of the tensor. In this paper, we consider online low-rank estimation of tensor data where the multidimensional data are revealed sequentially. Induced by the recently proposed tensor-tensor product (t-product), we rigorously deduce the tensor max-norm and formulate the tensor max-norm into an equivalent tensor factorization form, where the factors consist of a tensor basis component and a coefficient one. With this formulation, we develop an online max-norm regularized tensor decomposition (OMRTD) method by alternatively optimizing over the basis component and the coefficient tensor. The algorithm is scalable to the large-scale setting and the sequence of the solutions produced by OMRTD converges to a stationary point of the expected loss function asymptotically. Further, we extend OMRTD for tensor completion. Numerical experiments demonstrate encouraging results for the effectiveness and robustness of our algorithm.

Recently, tensor low-rank representation (TLRR) has become a popular tool for tensor data recovery and clustering, due to its empirical success and theoretical guarantees. However, existing TLRR methods consider Gaussian or gross sparse noise, inevitably leading to performance degradation when the tensor data are contaminated by outliers or sample-specific corruptions. This paper develops an outlier-robust tensor low-rank representation (OR-TLRR) method that provides outlier detection and tensor data clustering simultaneously based on the t-SVD framework. For tensor observations with arbitrary outlier corruptions, OR-TLRR has provable performance guarantee for exactly recovering the row space of clean data and detecting outliers under mild conditions. Moreover, an extension of OR-TLRR is proposed to handle the case when parts of the data are missing. Finally, extensive experimental results on synthetic and real data demonstrate the effectiveness of the proposed algorithms.

Tensor low-rank representation (TLRR) has attracted increasing attention in recent years due to its effectiveness in capturing the intrinsic low-rank structure of tensor data. However, it is known that TLRR suffers from high computational complexity for large-scale data because it minimizes the tensor rank of the representation tensor whose size is proportional to the sample size. This paper develops a streaming algorithm—termed online low-rank tensor subspace clustering (OLRTSC)—for low-rank tensor data recovery and clustering based on the tensor singular value decomposition (t-SVD) algebraic framework. The key idea of OLRTSC is the non-convex reformulation of the objective function of TLRR by decomposing the tensor nuclear norm into an explicit tensor product of two low-rank tensors, which can be solved by leveraging the stochastic optimization technique. Compared to batch TLRR, OLRTSC is online by nature, can handle dynamic data, avoids computing t-SVD of the representation tensor, and reduces the storage cost significantly. This paper provides the theoretical guarantee that the sequence of the solutions produced by OLRTSC converges almost surely to a stationary point of the objective function. Moreover, an extension of OLRTSC is also proposed to handle the case when parts of the data are missing. Finally, experimental results on both synthetic and real data demonstrate the efficiency and robustness of the proposed approaches.

In this paper, a new submodule clustering method for imaging (2-D) data is proposed. Unlike most existing clustering methods that first convert such data into vectors as preprocessing, the proposed method arranges the data samples as lateral slices of a third-order tensor. Our algorithm is based on the union-of-free-submodules model and the samples are represented using t-product in the third-order tensor space. First, we impose a low-rank constraint on the representation tensor to capture the principle information of data. By incorporating manifold regularization into the tensor factorization, the proposed method explicitly exploits the local manifold structure of data. Meanwhile, a segmentation dependent term is employed to integrate the two pipeline steps of affinity learning and spectral clustering into a unified optimization framework. The proposed method can be efficiently solved based on the alternating direction method of multipliers and spectral clustering. Finally, a nonlinear extension is proposed to handle data drawn from a mixture of nonlinear manifolds. Extensive experimental results on five real-world image datasets confirm the effectiveness of the proposed methods.

This paper proposes a new streaming algorithm to learn low-rank structures of tensor data using the recently proposed tensor-tensor product (t-product) and tensor singular value decomposition (t-SVD) algebraic framework. It reformulates the tensor low-rank representation (TLRR) problem using the equivalent bifactor model of the tensor nuclear norm, where the tensor dictionary is updated based on the newly collected data and representations. Compared to TLRR, the proposed method processes tensor data in an online fashion and makes the memory cost independent of the data size. Experimental results on three benchmark datasets demonstrate the superior performance, efficiency and robustness of the proposed algorithm over state-of-the-art methods.

Representation of human actions as a sequence of human body movements or action attributes enables the development of models for human activity recognition and summarization. We present an extension of the low-rank representation (LRR) model, termed the clustering-aware structure-constrained low-rank representation (CS-LRR) model, for unsupervised learning of human action attributes from video data. Our model is based on the union-of-subspaces (UoS) framework, and integrates spectral clustering into the LRR optimization problem for better subspace clustering results. We lay out an efficient linear alternating direction method to solve the CS-LRR optimization problem. We also introduce a hierarchical subspace clustering approach, termed hierarchical CS-LRR, to learn the attributes without the need for a priori specification of their number. By visualizing and labeling these action attributes, the hierarchical model can be used to semantically summarize long video sequences of human actions at multiple resolutions. A human action or activity can also be uniquely represented as a sequence of transitions from one action attribute to another, which can then be used for human action recognition. We demonstrate the effectiveness of the proposed model for semantic summarization and action recognition through comprehensive experiments on five real-world human action datasets.

In this paper, a new clustering algorithm for two-dimensional data is proposed. Unlike most conventional clustering methods which are derived for dealing with matrices, the proposed algorithm performs clustering in a third-order tensor space. The images are then assumed to be drawn from a mixture of low-dimensional free submodules. The proposed method integrates spectral clustering into the optimization problem, thereby overcomes the shortcomings of existing techniques by its ability to perform optimal clustering of the submodules. An efficient algorithm via a combination of an alternating direction method of multipliers and spectral clustering is developed to find the representation tensor and the segmentation simultaneously. The effectiveness of the proposed method is demonstrated through experiments on three image datasets.

This letter proposes an algorithm for clustering of two-dimensional data. Instead of "flattening" data into vectors, the proposed algorithm keeps samples as matrices and stores them as lateral slices in a third-order tensor. It is then assumed that the samples lie near a union of free submodules and their representations under this model are obtained by imposing a low tensor-rank constraint and a structural constraint on the representation tensor. Clustering is carried out using an affinity matrix calculated from the representation tensor. Effectiveness of the proposed algorithm and its superiority over existing methods are demonstrated through experiments on two image datasets.

This paper studies the problem of learning human action attributes based on union-of-subspaces model. It puts forth an extension of the low-rank representation (LRR) model, termed the hierarchical clustering-aware structure-constrained low-rank representation (HCS-LRR) model, for unsupervised learning of human action attributes from video data. The effectiveness of the proposed model is demonstrated through experiments on five human action datasets for action recognition.

The advent of ubiquitous mobile devices has provided us with an abundant spatio-temporal data source that helps us understand human mobility. The big data generated from mobile devices can be distributed at different locations and it is always infeasible to aggregate the data from multiple data collection centers into one location due to communication and privacy considerations. This paper studies human mobility patterns by learning data-adaptive representations for cellular network data that are distributed across a set of interconnected nodes. It proposes a distributed algorithm, termed cloud NN-K-SVD, for collaboratively learning a sparsifying dictionary (i.e., overcomplete basis) from the data without exchanging data samples between different nodes. The effectiveness of cloud NN-K-SVD is demonstrated through experiments on anonymized Call Detail Records from Columbus, OH.

This paper addresses the problem of learning meaningful human action attributes from high-dimensional video sequences based on union-of-subspaces (UoS) model. The model hypothesizes that each action attribute is represented by a subspace. It puts forth an extension of existing low-rank representation (LRR), termed the clustering-aware structure-constrained low-rank representation (CS-LRR) model, for unsupervised learning of human action attributes. The proposed CS-LRR model overcomes the shortcomings of existing techniques by its ability to handle disjoint subspaces, and by performing optimal spectral clustering of the subspaces. An efficient linear alternating direction method (LADM) is developed to solve the CS-LRR optimization problem. A human action or activity is represented as a sequence of transitions from one action attribute to another and can be uniquely represented by a subspace transition vector. These subspace transition vectors are used for human action recognition. The effectiveness of the proposed model is demonstrated through experiments on two real-world datasets for action recognition.

Modern information processing relies on the axiom that high-dimensional data lie near low-dimensional geometric structures. This paper revisits the problem of data-driven learning of these geometric structures and puts forth two new nonlinear geometric models for data describing “related” objects/phenomena. The first one of these models straddles the two extremes of the subspace model and the union-of-subspaces model, and is termed the metric-constrained union-of-subspaces (MC-UoS) model. The second one of these models—suited for data drawn from a mixture of nonlinear manifolds—generalizes the kernel subspace model, and is termed the metric-constrained kernel union-of-subspaces (MC-KUoS) model. The main contributions of this paper in this regard include the following. First, it motivates and formalizes the problems of MC-UoS and MC-KUoS learning. Second, it presents algorithms that efficiently learn an MC-UoS or an MC-KUoS underlying data of interest. Third, it extends these algorithms to the case when parts of the data are missing. Last, but not least, it reports the outcomes of a series of numerical experiments involving both synthetic and real data that demonstrate the superiority of the proposed geometric models and learning algorithms over existing approaches in the literature. These experiments also help clarify the connections between this work and the literature on (subspace and kernel k-means) clustering.

A hierarchical union-of-subspaces model is proposed for performing semi-supervised human activity summarization in large streams of video data. The union of low-dimensional subspaces model is used to learn meaningful action attributes from a collection of high-dimensional video sequences of human activities. An approach called hierarchical sparse subspace clustering (HSSC) is developed to learn this model from the data in an unsupervised manner by capturing the variations or movements of each action in different subspaces, which allow the human actions to be represented as sequences of transitions from one subspace to another. These transition sequences can be used for human action recognition. The action attributes can also be represented at multiple resolutions using the subspaces at different levels of the hierarchical structure. By visualizing and labeling these action attributes, the hierarchical model can be used to semantically summarize long video sequences of human actions at different scales. The effectiveness of the proposed model is demonstrated through experiments on three real-world human action datasets for action recognition and semantic summarization of the actions using different resolutions of the action attributes.

Sparse representations of images in overcomplete bases (i.e., redundant dictionaries) have many applications in computer vision and image processing. Recent works have demonstrated improvements in image representations by learning a dictionary from training data instead of using a predefined one. But learning a sparsifying dictionary can be computationally expensive in the case of a massive training set. This paper proposes a new approach, termed active screening, to overcome this challenge. Active screening sequentially selects subsets of training samples using a simple heuristic and adds the selected samples to a "learning pool," which is then used to learn a newer dictionary for improved representation performance. The performance of the proposed active dictionary learning approach is evaluated through numerical experiments on real-world image data; the results of these experiments demonstrate the effectiveness of the proposed method.

This paper addresses the problem of learning a collection of nonlinear manifolds. Inspired by kernel methods, it puts forth a generalization of the kernel subspace model, termed the Metric-Constrained Kernel Union-of-Subspaces (MC-KUoS) model. It then develops an iterative method for learning of an MC-KUoS whose solution is based on the data representation capability of the manifolds and distances between subspaces in the kernel (feature) space. The proposed method (when using Gaussian and polynomial kernels) outperforms existing competitive state-of-the-art methods for real-world image denoising, which shows the benefits of the MC-KUoS model and the proposed denoising approach.

This paper studies the problem of matched subspace detection in high-dimensional feature space where the signal in the input space is partially observed. We present a test statistic for our detection problem using kernel functions and provide kernel function value estimators with missing data for different kernels. The test statistic can be calculated approximately with estimated kernel function values. We also give theoretical results regarding the kernel function value and test statistic estimation. Numerical experiments involving both Gaussian and polynomial kernels show the efficacy of the proposed kernel function value estimator and resulting subspace detector.

This paper revisits the problem of data-adaptive learning of geometric signal structures based on the Union-of-Subspaces (UoS) model. In contrast to prior work, it motivates and investigates an extension of the classical UoS model, termed the Metric-Constrained Union-of-Subspaces (MC-UoS) model. In this regard, it puts forth two iterative methods for data-adaptive learning of an MC-UoS in the presence of complete and missing data. The proposed methods outperform existing approaches to learning a UoS in numerical experiments involving both synthetic and real data, which demonstrates effectiveness of both an MC-UoS model and the proposed methods.

In this paper, computer-based techniques for stylistic analysis of paintings are applied to the five panels of the 14th century Peruzzi Altarpiece by Giotto di Bondone. Features are extracted by combining a dual-tree complex wavelet transform with a hidden Markov tree (HMT) model. Hierarchical clustering is used to identify stylistic keywords in image patches, and keyword frequencies are calculated for sub-images that each contains many patches. A generative hierarchical Bayesian model learns stylistic patterns of keywords; these patterns are then used to characterize the styles of the sub-images; this in turn, permits to discriminate between paintings. Results suggest that such unsupervised probabilistic topic models can be useful to distill characteristic elements of style.