Search

There is growing interest to extend low-rank matrix decompositions to multi-way arrays, or tensors. One fundamental low-rank tensor decomposition is the canonical polyadic decomposition (CPD). The challenge of fitting a low-rank, nonnegative CPD model to Poisson-distributed count data is of particular interest. Several popular algorithms use local search methods to approximate the maximum likelihood estimator (MLE) of the Poisson CPD model. This work presents two new algorithms that extend state-of-the-art local methods for Poisson CPD. Hybrid GCP-CPAPR combines Generalized Canonical Decomposition (GCP) with stochastic optimization and CP Alternating Poisson Regression (CPAPR), a deterministic algorithm, to increase the probability of converging to the MLE over either method used alone. Restarted CPAPR with SVDrop uses a heuristic based on the singular values of the CPD model unfoldings to identify convergence toward optimizers that are not the MLE and restarts within the feasible domain of the optimization problem, thus reducing overall computational cost when using a multi-start strategy. We provide empirical evidence that indicates our approaches outperform existing methods with respect to converging to the Poisson CPD MLE. [ABSTRACT FROM AUTHOR]

Latency overhead in distributed-memory parallel CPD-ALS scales with the number of processors, limiting the scalability of computing CPD of large irregularly sparse tensors. This overhead comes in the form of sparse reduce and expand operations performed on factor-matrix rows via point-to-point messages. We propose to hide the latency overhead through embedding all of the point-to-point messages incurred by the sparse reduce and expand into dense collective operations which already exist in the CPD-ALS. The conventional parallel CPD-ALS algorithm is not amenable for embedding so we propose a computation/communication rearrangement to enable the embedding. We embed the sparse expand and reduce into a hypercube-based ALL-REDUCE operation to limit the latency overhead to $O(\log _2 K)$ O (log 2 K) for a $K$ K -processor system. The embedding comes with the cost of increased bandwidth overhead due to the multi-hop routing of factor-matrix rows during the embedded-ALL-REDUCE. We propose an embedding scheme that takes advantage of the expand/reduce properties to reduce this overhead. Furthermore, we propose a novel recursive bipartitioning framework that enables simultaneous hypergraph partitioning and subhypergraph-to-subhypercube mapping to achieve subtensor-to-processor assignment with the objective of reducing the bandwidth overhead during the embedded-ALL-REDUCE. We also propose a bin-packing-based algorithm for factor-matrix row to processor assignment aiming at reducing processors’ maximum send and receive volumes during the embedded-ALL-REDUCE. Experiments on up to 4096 processors show that the proposed framework scales significantly better than the state-of-the-art point-to-point method. [ABSTRACT FROM AUTHOR]

The Canonical Polyadic Decomposition (CPD), which decomposes a tensor into a sum of rank one terms, plays an important role in signal processing and machine learning. In this paper we extend the CPD framework to the more general case of bilinear factorizations subject to monomial equality constraints. This includes extensions of multilinear algebraic uniqueness conditions originally developed for the CPD. We obtain a deterministic uniqueness condition that admits a constructive interpretation. Computationally, we reduce the bilinear factorization problem into a CPD problem, which can be solved via a matrix EigenValue Decomposition (EVD). Under the given conditions, the discussed EVD-based algorithms are guaranteed to return the exact bilinear factorization. Finally, we make a connection between bilinear factorizations subject to monomial equality constraints and the coupled block term decomposition, which allows us to translate monomial structures into low-rank structures. [ABSTRACT FROM AUTHOR]

Decomposing tensors into simple terms is often an essential step toward discovering and understanding underlying processes or toward compressing data. However, storing the tensor and computing its decomposition is challenging in a large-scale setting. Though in many cases a tensor is structured, it can be represented using few parameters: a sparse tensor is determined by the positions and values of its nonzeros, a polyadic decomposition by its factor matrices, a Tensor Train by its core tensors, a Hankel tensor by its generating vector, etc. The complexity of tensor decomposition algorithms can be reduced significantly in terms of time and memory if these effcient representations are exploited directly. Only a few core operations such as norms and inner products need to be specialized to achieve this, thereby avoiding the explicit construction of multiway arrays. To improve the interpretability of tensor models, constraints are often imposed or multiple datasets are fused through joint factorizations. While imposing these constraints prohibits the use of traditional compression techniques, our framework allows constraints and compression, as well as other effcient representations, to be handled trivially as the underlying optimization variables do not change. To illustrate this, large-scale nonnegative tensor factorization is performed using MLSVD and Tensor Train compression. We also show how vector and matrix data can be analyzed using tensorization while keeping a vector or matrix complexity through the concept of implicit tensorization, as illustrated for Hankelization and Läwnerization. The concepts and numerical properties are extensively investigated through experiments. [ABSTRACT FROM AUTHOR]

Objective: Magnetic resonance spectroscopic imaging (MRSI) signals are often corrupted by residual water and artifacts. Residual water suppression plays an important role in accurate and efficient quantification of metabolites from MRSI. A tensor-based method for suppressing residual water is proposed. Methods: A third-order tensor is constructed by stacking the Löwner matrices corresponding to each MRSI voxel spectrum along the third mode. A canonical polyadic decomposition is applied on the tensor to extract the water component and to, subsequently, remove it from the original MRSI signals. Results: The proposed method applied on both simulated and in-vivo MRSI signals showed good water suppression performance. Conclusion: The tensor-based Löwner method has better performance in suppressing residual water in MRSI signals as compared to the widely used subspace-based Hankel singular value decomposition method. Significance: A tensor method suppresses residual water simultaneously from all the voxels in the MRSI grid and helps in preventing the failure of the water suppression in single voxels. [ABSTRACT FROM AUTHOR]

Tensor decomposition is widely used in the analysis of multi-dimensional data. The canonical polyadic decomposition (CPD) is one of the most popular decomposition methods and commonly found by the CPD-ALS algorithm. High computational and memory costs of CPD-ALS necessitate the use of a distributed-memory-parallel algorithm for efficiency. The medium-grain CPD-ALS algorithm, which adopts multi-dimensional cartesian tensor partitioning, is one of the most successful distributed CPD-ALS algorithms for sparse tensors. This is because cartesian partitioning imposes nice upper bounds on communication overheads. However, this model does not utilize the sparsity pattern of the tensor to reduce the total communication volume. The objective of this work is to fill this literature gap. We propose a novel hypergraph-partitioning model, CartHP, whose partitioning objective correctly encapsulates the minimization of total communication volume of multi-dimensional cartesian tensor partitioning. Experiments on twelve real-world tensors using up to 1024 processors validate the effectiveness of the proposed CartHP model. Compared to the baseline medium-grain model, CartHP achieves average reductions of 52, 43 and 24 percent in total communication volume, communication time and overall runtime of CPD-ALS, respectively. [ABSTRACT FROM AUTHOR]

Tensor decompositions such as the canonical polyadic decomposition (CPD) or the block term decomposition (BTD) are basic tools for blind signal separation. Most of the literature concerns instantaneous mixtures/memoryless channels. In this paper, we focus on convolutive extensions. More precisely, we present a connection between convolutive CPD/BTD models and coupled but instantaneous CPD/BTD. We derive a new identifiability condition dedicated to convolutive low-rank factorization problems. We explain that under this condition, the convolutive extension of CPD/BTD can be computed by means of an algebraic method, guaranteeing perfect source separation in the noiseless case. In the inexact case, the algorithm can be used as a cheap initialization for an optimization-based method. We explain that, in contrast to the memoryless case, convolutive signal separation is in certain cases possible despite only two-way diversities (e.g., space $\times$ time). [ABSTRACT FROM PUBLISHER]

Several applications in biomedical data processing, telecommunications, or chemometrics can be tackled by computing a structured tensor decomposition. In this paper, we focus on tensor decompositions with two or more block-Hankel factors, which arise in blind multiple-input-multiple-output (MIMO) convolutive system identification. By assuming statistically independent inputs, the blind system identification problem can be reformulated as a Hankel structured tensor decomposition. By capitalizing on the available block-Hankel and tensorial structure, a relaxed uniqueness condition for this structured decomposition is obtained. This condition is easy to check, yet very powerful. The uniqueness condition also forms the basis for two subspace-based algorithms, able to blindly identify linear underdetermined MIMO systems with finite impulse response. [ABSTRACT FROM PUBLISHER]

In this letter, we aim to jointly separate the underdetermined mixtures of latent sources from two datasets, where the number of sources exceeds the number of observations in each dataset. Currently available blind source separation (BSS) methods, including joint blind source separation (JBSS) and underdetermined blind source separation (UBSS), cannot address this underdetermined problem effectively. We exploit the second-order statistics of observations and introduce a novel BSS method, termed as underdetermined joint blind source separation (UJBSS). Considering the dependence information between two datasets, the problem of jointly estimating the mixing matrices is tackled via canonical polyadic (CP) decomposition of a specialized tensor in which a set of spatial covariance matrices are stacked. Furthermore, the estimated mixing matrices are used to recover the sources from each dataset separately. Numerical results demonstrate the competitive performance of the proposed method when compared to a commonly used JBSS method, multiset canonical correlation analysis (MCCA), and the single-set UBSS method, UBSS with free active sources (UBSS-FAS). [ABSTRACT FROM AUTHOR]

For the analysis of large-scale datasets one often assumes simple structures. In the case of tensors, a decomposition in a sum of rank-1 terms provides a compact and informative model. Finding this decomposition is intrinsically more difficult than its matrix counterpart. Moreover, for large-scale tensors, computational difficulties arise due to the curse of dimensionality. The randomized block sampling canonical polyadic decomposition method presented here combines increasingly popular ideas from randomization and stochastic optimization to tackle the computational problems. Instead of decomposing the full tensor at once, updates are computed from small random block samples. Using step size restriction the decomposition can be found up to near optimal accuracy, while reducing the computation time and number of data accesses significantly. The scalability is illustrated by the decomposition of a synthetic 8 TB tensor and a real life 12.5 GB tensor in a few minutes on a standard laptop. [ABSTRACT FROM PUBLISHER]

CANDECOMP/PARAFAC (CP) approximates multiway data by sum of rank-1 tensors. Unlike matrix decomposition, the procedure which estimates the best rank-R tensor approximation through R sequential best rank-1 approximations does not work for tensors, because the deflation does not always reduce the tensor rank. In this paper, we propose a novel deflation method for the problem. When one factor matrix of a rank-R CP decomposition is of full column rank, the decomposition can be performed through (R-1) rank-1 reductions. At each deflation stage, the residue tensor is constrained to have a reduced multilinear rank. For decomposition of order-3 tensors of size R\times R\times R and rank-R, estimation of one rank-1 tensor has a computational cost of \cal O(R^3) per iteration which is lower than the cost \cal O(R^4) of the ALS algorithm for the overall CP decomposition. The method can be extended to tracking one or a few rank-one tensors of slow changes, or inspect variations of common patterns in individual datasets. [ABSTRACT FROM PUBLISHER]

We present structured data fusion (SDF) as a framework for the rapid prototyping of knowledge discovery in one or more possibly incomplete data sets. In SDF, each data set—stored as a dense, sparse, or incomplete tensor—is factorized with a matrix or tensor decomposition. Factorizations can be coupled, or fused, with each other by indicating which factors should be shared between data sets. At the same time, factors may be imposed to have any type of structure that can be constructed as an explicit function of some underlying variables. With the right choice of decomposition type and factor structure, even well-known matrix factorizations such as the eigenvalue decomposition, singular value decomposition and QR factorization can be computed with SDF. A domain specific language (DSL) for SDF is implemented as part of the software package Tensorlab, with which we offer a library of tensor decompositions and factor structures to choose from. The versatility of the SDF framework is demonstrated by means of four diverse applications, which are all solved entirely within Tensorlab’s DSL. [ABSTRACT FROM PUBLISHER]

This paper presents a Cramér-Rao lower bound (CRLB) on the variance of unbiased estimates of factor matrices in Canonical Polyadic (CP) or CANDECOMP/PARAFAC (CP) decompositions of a tensor from noisy observations, (i.e., the tensor plus a random Gaussian i.i.d. tensor). A novel expression is derived for a bound on the mean square angular error of factors along a selected dimension of a tensor of an arbitrary dimension. The expression needs less operations for computing the bound, O(NR^6), than the best existing state-of-the art algorithm, O(N^3R^6) operations, where N and R are the tensor order and the tensor rank. Insightful expressions are derived for tensors of rank 1 and rank 2 of arbitrary dimension and for tensors of arbitrary dimension and rank, where two factor matrices have orthogonal columns. [ABSTRACT FROM PUBLISHER]