Abstract
The canonical polyadic decomposition (CPD) of high-order tensors, also known as Candecomp/Parafac, is very useful for representing and analyzing multidimensional data. This paper considers a CPD model having structured matrix factors, as e.g. Toeplitz, Hankel or circulant matrices, and studies its associated estimation problem. This model arises in signal processing applications such as Wiener-Hammerstein system identification and cumulant-based wireless communication channel estimation. After introducing a general formulation of the considered structured CPD (SCPD), we derive closed-form expressions for the Cramér-Rao bound (CRB) of its parameters under the presence of additive white Gaussian noise. Formulas for special cases of interest, as when the CPD contains identical factors, are also provided. Aiming at a more relevant statistical evaluation from a practical standpoint, we discuss the application of our formulas in a Bayesian context, where prior distributions are assigned to the model parameters. Three existing algorithms for computing SCPDs are then described: a constrained alternating least squares (CALS) algorithm, a subspace-based solution and an algebraic solution for SCPDs with circulant factors. Subsequently, we present three numerical simulation scenarios, in which several specialized estimators based on these algorithms are proposed for concrete examples of SCPD involving circulant factors. In particular, the third scenario concerns the identification of a Wiener-Hammerstein system via the SCPD of an associated Volterra kernel. The statistical performance of the proposed estimators is assessed via Monte Carlo simulations, by comparing their Bayesian mean-square error with the expected CRB.
Introduction
Tensor decompositions, specifically the Canonical Polyadic Decomposition (CPD), are essential tools for analyzing multidimensional data across diverse fields. In signal processing applications like wireless communication or system modeling, the underlying physical properties often dictate that the factor matrices must possess specific linear structures, such as Toeplitz, Hankel, or circulant forms.
Despite the development of specialized algorithms to exploit these structures, two major gaps have persisted: the lack of clear performance benchmarks to assess statistical efficiency and the inherent instability of standard iterative methods, which often converge slowly or stall in local minima. This paper addresses these challenges by providing a rigorous framework for Structured CPD (SCPD), deriving new theoretical performance limits, and proposing robust "hybrid" algorithmic strategies.
Defining the Structured CPD Framework
The authors define an SCPD where factor matrices are constrained to a linear subspace spanned by a set of basis matrices. This general formulation allows for a unified treatment of various common structures encountered in engineering and physics.
By enforcing these structures, the number of parameters to estimate is significantly reduced. This acts as a form of regularization, theoretically lowering the "noise floor" of the estimation. The table above illustrates how different structures—ranging from unstructured to banded circulant—are formally integrated into the decomposition model.
Theoretical Performance Limits
A core contribution of this work is the derivation of closed-form expressions for the Cramér-Rao Bound (CRB). To provide a more practical benchmark, the authors extend this to a Bayesian context by calculating the Expected CRB (ECRB).
They demonstrate that for non-linear tensor models, the ECRB is a more robust and tighter lower bound than traditional Bayesian bounds like the Van Trees bound. The ECRB remains valid even when strict regularity conditions are not met, providing a reliable target for evaluating the statistical efficiency of new estimators.
Algorithmic Strategies: From Iterative to Hybrid
The paper evaluates three primary approaches to solving the SCPD problem:
- Constrained Alternating Least Squares (CALS): An iterative method that enforces the required structure at every step of the optimization.
- Algebraic/Subspace Solutions: Non-iterative, closed-form methods (such as AAS for circulant factors) that are computationally inexpensive but highly sensitive to noise.
- Hybrid Strategies: This approach uses fast algebraic methods to provide a "warm start" for iterative refinement via CALS or quasi-Newton BFGS optimization.
The simulations reveal that initialization is often the primary bottleneck; while standard CALS frequently fails with random starts, the hybrid approach consistently allows the optimizer to reach the theoretical performance limit (the ECRB).
Key Results and Applications
The framework was tested across several scenarios, including distinct circulant factors and symmetric models. A standout application was the identification of a Wiener-Hammerstein system via the decomposition of a Volterra kernel, which results in banded circulant factors.
Key findings include:
- Statistical Efficiency: In the Wiener-Hammerstein scenario, the hybrid "CPTOEP-CALS" estimator reached the ECRB at Signal-to-Noise Ratios (SNR) above ~11 dB.
- Computational Gains: Algebraic methods were found to be orders of magnitude faster than iterative ones (e.g., ~1ms vs. ~10s). The hybrid strategy captures the best of both worlds: the speed of algebraic initialization and the accuracy of iterative refinement.
- The Challenge of Symmetry: Symmetric models (where factors are identical) are significantly more difficult to solve and require specialized logic to avoid convergence issues.
Conclusion and Future Directions
While this work focuses primarily on third-order tensors, it establishes a foundation for structured decomposition that can be extended to higher orders. Future research may explore incorporating additional constraints common in data mining, such as non-negativity or sparsity, into this structured framework. By bridging the gap between theoretical bounds and practical algorithms, this paper provides a roadmap for more accurate and efficient multidimensional signal processing.
Summary updated