Identifying whether a mixed quantum state is uniquely determined among all states (UDA) by its local marginals is a basic problem in quantum information theory. We establish necessary and sufficient conditions under which several classes of multipartite mixed states are UDA by theirk-partite marginals. We also prove structural properties based on ranges and marginals, and formulate a recursive procedure for the determination of UDA states. We show that sufficiently high rank rules out unique determination from fixed-order marginals, implying that almost all multipartite mixed states are not UDA from such marginals. Finally, we completely characterize the additivity of bipartite UDA states, three-qubit and several families ofn-qubit product UDA states. These results clarify the boundary between UDA and non-UDA mixed states and provide a framework for local-marginal reconstruction and related certification tasks.

Nonnegative low-rank matrix approximation is an important technique in data analysis for extracting meaningful patterns from high-dimensional nonnegative data. This nonnegative low-rank approximation problem is studied and a new block-splitting method is developed in this paper. This new method enforces the low-rank constraint by utilizing QR decomposition and adopts a semismooth Newton method to address the related convex subproblems efficiently through the dual formulation of the nonnegative low-rank matrix approximation problem. Theoretical analysis confirms the convergence of the new method. Several real datasets are used to demonstrate the efficiency of the proposed method.

Abstract. Block term decomposition (BTD), which decomposes a third-order tensor into multiple terms with the multilinear rank [Formula: see text], has garnered increasing attention for high-dimensional image representation. The idea of decomposing the tensor into multiple terms has the potential to reveal the underlying different structures of the original tensor. However, BTD practically struggles to reveal these underlying different structures in the original domain, which locks the potential of the BTD. To address this problem, we propose a dictionary-based BTD (DBTD) for third-order tensors by revisiting the BTD from the convolutional dictionary learning perspective, which can better reveal the underlying different structures of the original tensor. The proposed DBTD decomposes the original tensor into multiple different terms, where each term is represented by the convolution of an adaptive dictionary and the corresponding low-rank coefficient. Herein, the adaptive dictionaries can represent distinct patterns and contribute to the DBTD’s ability to reveal the underlying different structures of the original tensor. Moreover, we establish the essential uniqueness guarantee for the DBTD. Empowered with DBTD, we suggest a high-dimensional image recovery model and develop an efficiently solving algorithm with a convergence guarantee. Numerical results on real-world high-dimensional images demonstrate that the proposed DBTD outperforms other competing decompositions in image recovery and benefits subsequent image applications.

The hierarchical alternating least squares (HALS) algorithms are powerful tools for nonnegative matrix factorization (NMF), among which the Fast-HALS, proposed in [A. Cichocki and A.-H. Phan, 2009], is one of the most efficient. This paper investigates the convergence of Fast-HALS. First, a more general weak convergence (converged subsequences exist and converge to the stationary point set) is established without any assumption, while most existing results assume all the columns of iterates are strictly away from the origin. Then, a simplified strong convergence (the entire sequence converges to a stationary point) proof is provided. The existing strong convergence is attributed to the block prox-linear (BPL) method, which is a more general framework including Fast-HALS as a special case. So, the convergence proof under BPL is quite complex. Our simplified proof explores the structure of Fast-HALS and can be regarded as a complement to the results under BPL. In addition, some numerical verifications are presented.

In this article, we study the symmetric nonnegative matrix factorization (SNMF) which is a powerful tool in data mining for dimension reduction and clustering. The main contributions of the present work include: (i) a new descent direction for the rank-one SNMF is derived and a strategy for choosing the step size along this descent direction is established; (ii) a progressive hierarchical alternating least squares (PHALS) method for SNMF is developed, which is parameter-free and updates the variables column by column. Moreover, every column is updated by solving a rank-one SNMF subproblem; and (iii) the convergence to the Karush-Kuhn-Tucker (KKT) point set (or the stationary point set) is proved for PHALS. Several synthetical and real data sets are tested to demonstrate the effectiveness and efficiency of the proposed method. Our PHALS provides better performance in terms of the computational accuracy, the optimality gap, and the CPU time, compared with a number of state-of-the-art SNMF methods.

Solving least squares (LS) problems is a major topic in many applications. With recent data explosion, traditional approach is no longer suitable while working with large datasets, instead, randomized algorithms become popular in addressing this issue. In this article we propose a new randomized algorithm - sparse subsampled randomized Hadamard transform (SpSRHT) for solving overdetermined least squares problems. Its unique block structure connects two most commonly used randomized algorithms subsampled randomized Hadamard transform (SRHT) and sparse subspace embedding (SpEmb) and creates a general framework which contains them as special cases. We have shown theoretically that SpSRHT with different parameters reaches the relative-error bound with sketch size ranging from the sketch size required by SpEmb to SRHT. The new algorithm closes the gap between SRHT and SpEmb which provides the possibility of balancing accuracy and efficiency demonstrated in them. This advantage of SpSRHT is also well illustrated in our numerical experiments.

The existing cloud removal methods either need a cloud mask as prior knowledge or detect clouds before cloud removal processing, i.e., the detection and removal processes are separate. In this article, we propose a box-constrained (BC) smooth low-rank plus group sparse model to simultaneously detect and remove clouds, by formulating the degraded data as the summation of image and cloud components. For the cloud component, we propose a group sparse function along the spectral dimension. This is motivated by our observations that: 1) one tube is contaminated by clouds if any pixels of this tube are contaminated by clouds; 2) the positions of tubes, which are taken at different times, contaminated by clouds are different. For the image component, we propose to use a tensor rank based on the tensor singular value decomposition. The tensor rank characterizes the global property of the image component and could not keep the cloud-free information unchanged. To address the problem, we introduce a BC on the image component to force its cloud-free information to be equal to the corresponding values of observed data. Owing to the BC, the proposed model integrates the cloud detection and removal processes so that the two processes could promote each other and result in a promising result. To solve the proposed model, we develop an efficient algorithm that can generate the cloud mask, image component, and cloud component alternately. Extensive experiments on synthetic and real data show that the proposed method is competitive compared with the completion and other cloud removal methods.

Recently a deterministic method, frequent directions (FD) is proposed to solve the high dimensional low rank approximation problem. It works well in practice, but experiences high computational cost. In this paper, we establish a fast frequent directions algorithm for the low rank approximation problem, which implants a randomized algorithm, sparse subspace embedding (SpEmb) in FD. This new algorithm makes use of FD's natural block structure and sends more information through SpEmb to each block in FD. We prove that our new algorithm produces a good low rank approximation with a sketch of size linear on the rank approximated. Its effectiveness and efficiency are demonstrated by the experimental results on both synthetic and real world datasets, as well as applications in network analysis.

Linear discriminant analysis (LDA) as a well-known supervised dimensionality reduction method has been widely applied in many fields. However, the lack of sparsity in the LDA solution makes interpretation of the results challenging. In this paper, we propose a new model for sparse uncorrelated LDA (ULDA). Our model is based on the characterization of all solutions of the generalized ULDA. We incorporate sparsity into the ULDA transformation by seeking the solution with minimum ℓ1-norm from all minimum dimension solutions of the generalized ULDA. The problem is then formulated as an ℓ1-minimization problem with orthogonality constraint. To solve this problem, we devise two algorithms: 1) by applying the linearized alternating direction method of multipliers and 2) by applying the accelerated linearized Bregman method. Simulation studies and high-dimensional real data examples demonstrate that our algorithms not only compute extremely sparse solutions but also perform well in classification.

It has always been a challenging task to develop a fast and an efficient incremental linear discriminant analysis (ILDA) algorithm. For this purpose, we conduct a new study for linear discriminant analysis (LDA) in this paper and develop a new ILDA algorithm. We propose a new batch LDA algorithm called LDA/QR. LDA/QR is a simple and fast LDA algorithm, which is obtained by computing the economic QR factorization of the data matrix followed by solving a lower triangular linear system. The relationship between LDA/QR and uncorrelated LDA (ULDA) is also revealed. Based on LDA/QR, we develop a new incremental LDA algorithm called ILDA/QR. The main features of our ILDA/QR include that: 1) it can easily handle the update from one new sample or a chunk of new samples; 2) it has efficient computational complexity and space complexity; and 3) it is very fast and always achieves competitive classification accuracy compared with ULDA algorithm and existing ILDA algorithms. Numerical experiments based on some real-world data sets demonstrate that our ILDA/QR is very efficient and competitive with the state-of-the-art ILDA algorithms in terms of classification accuracy, computational complexity, and space complexity.

In this paper, we develop a novel approach for sparse uncorrelated linear discriminant analysis (ULDA). Our proposal is based on characterization of all solutions of the generalized ULDA. We incorporate sparsity into the ULDA transformation by seeking the solution with minimum \ell_1-norm from all minimum dimension solutions of the generalized ULDA. The problem is then formulated as a \ell_1-minimization problem and is solved by accelerated linearized Bregman method. Experiments on high-dimensional gene expression data demonstrate that our approach not only computes extremely sparse solutions but also performs well in classification. Experimental results also show that our approach can help for data visualization in low-dimensional space.

In this paper, we study canonical correlation analysis (CCA), which is a powerful tool in multivariate data analysis for finding the correlation between two sets of multidimensional variables. The main contributions of the paper are: 1) to reveal the equivalent relationship between a recursive formula and a trace formula for the multiple CCA problem, 2) to obtain the explicit characterization for all solutions of the multiple CCA problem even when the corresponding covariance matrices are singular, 3) to develop a new sparse CCA algorithm, and 4) to establish the equivalent relationship between the uncorrelated linear discriminant analysis and the CCA problem. We test several simulated and real-world datasets in gene classification and cross-language document retrieval to demonstrate the effectiveness of the proposed algorithm. The performance of the proposed method is competitive with the state-of-the-art sparse CCA algorithms.

A sparse representation-based classifier (SRC) is developed and shows great potential for real-world face recognition. This paper presents a dimensionality reduction method that fits SRC well. SRC adopts a class reconstruction residual-based decision rule, we use it as a criterion to steer the design of a feature extraction method. The method is thus called the SRC steered discriminative projection (SRC-DP). SRC-DP maximizes the ratio of between-class reconstruction residual to within-class reconstruction residual in the projected space and thus enables SRC to achieve better performance. SRC-DP provides low-dimensional representation of human faces to make the SRC-based face recognition system more efficient. Experiments are done on the AR, the extended Yale B, and PIE face image databases, and results demonstrate the proposed method is more effective than other feature extraction methods based on the SRC.

One of the most important problems for the study of singular distributed parameter systems is the well-posedness. Not only is it very important for the study of stability of singular distributed parameter systems, but also it is the theoretic basis for the study of the related problem of optimal control. In this paper, the concepts and the properties of generalized operator semigroup(GOS) and generalized integral semigroup(GIS) are given in Hilbert space, the solving problem of the non-homogeneous singular distributed parameter system is discussed by the concepts and the properties of GOS and GIS in Hilbert space, and some important results of the two classes of singular distributed parameter systems are given.

The sparse representation-based classifier (SRC) has been developed and shows great potential for pattern classification. This paper aims to gain a discriminative projection such that SRC achieves the optimum performance in the projected pattern space. We use the decision rule of SRC to steer the design of a dimensionality reduction method, which is coined the sparse representation classifier steered discriminative projection (SRC-DP). SRC-DP matches SRC optimally in theory. Experiments are done on the AR and extended Yale B face image databases, and results show the proposed method is more effective than other dimensionality reduction methods with respect to the sparse representation-based classifier.