Signal Processing

CP Decomposition

Q: How does CP decomposition differ from singular value decomposition?

The SVD applies to two-way matrices and is rotationally ambiguous: any orthogonal rotation of the singular vectors yields another valid factorization, so the components are not unique without an external constraint such as orthogonality. The CP decomposition applies to three-way and higher tensors, and under Kruskal's condition (k_A + k_B + k_C >= 2R + 2, where k denotes the Kruskal rank of each factor matrix and R is the tensor rank) it is essentially unique up to scaling and permutation of the rank-one terms. This uniqueness is why CP recovers the actual physical factors, such as steering vectors versus delay signatures, without requiring the factors to be orthogonal. In array processing this lets a single CP fit jointly separate spatial, temporal, and Doppler signatures that an SVD or eigenvalue method would mix together.

Q: How is the CP model fitted to measured array data?

The standard workhorse is alternating least squares (ALS). The R-component model is written in matricized form using the Khatri-Rao (column-wise Kronecker) product, then each factor matrix A, B, and C is updated in turn while the other two are held fixed, solving a linear least-squares problem at each step. ALS is repeated until the relative change in fit error falls below a tolerance, typically 1e-6 to 1e-8, which often takes 20 to several hundred iterations depending on conditioning and the presence of nearly collinear factors. Initialization commonly uses the generalized eigenvalue (GEVD) or direct trilinear decomposition solution to avoid local minima and swamps. For RF arrays the columns of the spatial factor are then matched to a steering-vector manifold to read off the angles of arrival, giving a closed-form estimate without a 2-D peak search.

Q: What tensor rank can a CP decomposition resolve with an N-element array?

For a third-order tensor built from an N-element array across T snapshots and K subarrays or frequency bins, the number of separable sources R is bounded by Kruskal uniqueness rather than by N alone. A classic result for generic factors gives identifiability up to roughly R = R, which can exceed the N-1 sources a conventional subspace method resolves from an N-element aperture. In practice a 10-element array exploiting both spatial diversity and a second diversity dimension (polarization, frequency, or time) can identify on the order of 20 to 40 sources, well beyond the 9 a single-snapshot MUSIC fit would handle. The trade-off is sensitivity to factor collinearity and to model-order error, so R is usually estimated with a core-consistency (CORCONDIA) check or an information criterion.

/see-pee dee-kom-puh-zish-uhn/ (CANDECOMP/PARAFAC)

Short for canonical polyadic (also called CANDECOMP or PARAFAC), this tensor decomposition writes a multi-way data array as a minimal sum of R rank-one outer products, one per source or signal component. Unlike a matrix factorization, the model is essentially unique up to scaling and permutation when Kruskal's condition holds, so it recovers the true physical factors (steering vectors, delays, Doppler signatures) without an orthogonality constraint. That property makes CP a powerful tool for closed-form DOA estimation and multidimensional harmonic retrieval, often resolving more sources than a single-snapshot subspace method built on the same N-element aperture. The factor matrices are typically fitted by alternating least squares and matched against the array manifold to read off arrival angles.

Category: Signal Processing

Tensor order: 3rd or higher

Uniqueness: k_A+k_B+k_C ≥ 2R+2

Why Tensors Beat Matrices in Array Processing

Most classical array methods, including the covariance-based subspace techniques, work on two-way data: a snapshot matrix of element outputs versus time. Collapsing the data into a single matrix discards structure. When the same wavefronts are observed across several diversity dimensions at once (multiple subarrays, polarizations, frequency bins, or coherent processing intervals), the measurements naturally form a three-way or higher tensor, and CP decomposition is the tool that exploits that structure. Each source contributes one rank-one term whose factor vectors are exactly the source's signature along each mode. Because the decomposition is essentially unique under mild conditions, those signatures come out cleanly separated, even when the underlying steering vectors are not orthogonal and even when there are more sources than a single dimension could resolve alone.

The contrast with the MUSIC subspace approach is the crux. A matrix SVD is only unique up to an arbitrary rotation of its singular vectors, so it can return any orthogonal mixture of the true components. The CP model has no such rotational freedom: once Kruskal's inequality on the Kruskal ranks of the factor matrices is satisfied, the rank-one terms are pinned down up to trivial scaling and reordering. This is the mathematical reason a CP-based estimator can read physical angles directly off the spatial factor matrix rather than performing a 2-D spectral search, and it underlies modern multidimensional ESPRIT-style and PARAFAC-DOA algorithms.

The cost is conditioning sensitivity. When two sources have nearly collinear signatures in every mode, the CP fit becomes ill-posed and alternating least squares can stall in long swamps where the error barely changes for many iterations. Practical implementations guard against this with line-search acceleration, good algebraic initialization, and a model-order check so the assumed rank R matches the data.

Governing Equations

Rank-one (canonical polyadic) model of a 3rd-order tensor:
X_ijk ≈ ∑_r=1^R a_ir × b_jr × c_kr

Outer-product form:
X ≈ ∑_r=1^R a_r ° b_r ° c_r

Matricized (mode-1) form via Khatri-Rao product (⊙):
X₍₁₎ ≈ A (C ⊙ B)^T

Kruskal uniqueness condition:
k_A + k_B + k_C ≥ 2R + 2

Where R = tensor rank (number of sources), a_r, b_r, c_r = factor vectors along each mode, k_(·) = Kruskal rank of each factor matrix. Example: factors with k_A=k_B=k_C=4 give a guaranteed-unique fit for up to R = 5 sources (12 ≥ 12).

CP Versus Other Subspace Estimators

Method	Data model	Uniqueness	Max sources (N elements)	Search	Notes
CP / PARAFAC	3-way+ tensor	Essentially unique (Kruskal)	> N−1 with extra diversity	None (closed form)	Handles non-orthogonal factors
MUSIC	2-way covariance	Subspace, needs ortho.	N−1	1-D / 2-D peak search	High resolution, search cost
ESPRIT	2-way, shift-invariant	Up to rotation	N−1	None (closed form)	Needs paired subarrays
Matrix SVD	2-way matrix	Up to rotation	min(rows, cols)	None	Rotationally ambiguous
Tucker / HOSVD	N-way tensor	Not unique (core)	Model dependent	None	Compression, not separation

Common Questions

Frequently Asked Questions

How does CP decomposition differ from singular value decomposition?

The SVD applies to two-way matrices and is unique only up to an arbitrary orthogonal rotation, so it can return any rotated mixture of the true components. CP applies to 3-way and higher tensors and, when Kruskal's condition k_A+k_B+k_C ≥ 2R+2 holds, is essentially unique up to scaling and permutation. That uniqueness recovers the actual physical factors (steering vectors versus delay or Doppler signatures) without forcing them to be orthogonal, letting one CP fit jointly separate spatial, temporal, and frequency signatures.

How is the CP model fitted to measured array data?

Alternating least squares (ALS) is the standard. The R-component model is matricized with the Khatri-Rao product, then each factor matrix A, B, C is updated in turn while the others are fixed, solving a linear least-squares step each time. Iteration continues until the relative fit-error change drops below about 1e−6 to 1e−8, often 20 to a few hundred iterations. Algebraic GEVD or trilinear initialization avoids local minima and swamps; the spatial factor columns are then matched to the steering-vector manifold to read off the angles of arrival.

What tensor rank can a CP decomposition resolve with an N-element array?

Identifiability is set by Kruskal uniqueness, not by N alone. For an I1 × I2 × I3 tensor with generic factors, separation is guaranteed up to roughly R ≤ floor((I1 × I2)/2) when I3 ≥ R, which can exceed the N−1 sources a single subspace method resolves. A 10-element array adding a second diversity dimension (polarization, frequency, or time) can identify on the order of 20 to 40 sources. The cost is sensitivity to collinear factors and model-order error, usually checked with CORCONDIA core consistency or an information criterion.

Related Terms

← Cp CP-OFDM →