The orthogonality that cannot be diagonal

A singular value decomposition delivers two things at the same time, and because it delivers them together nobody has to decide which one they wanted.

The factors are orthonormal: U and V have unit columns and no two of them are correlated, so the decomposition is a change of basis that no norm can see. The middle is diagonal: one number per direction, and the whole matrix is a sum of r independent rank-one pieces that do not interact.

Every use of the decomposition on this site leans on one or the other. Truncation leans on the second, because dropping a diagonal entry drops a whole term. Stability leans on the first, because an orthogonal change of basis does not amplify anything. For three indices the two come apart, and this essay is about which of them survives.

What survives: all-orthogonality #

The higher-order SVD’s factors are orthonormal by construction — they are left singular vectors — and its core inherits a real property from them, which is not diagonality and is not nothing.

Fix a mode k and slice the core perpendicular to it: for a three-index core that is rₖ matrices, one for each value of the k-th index. Those slices are mutually orthogonal, in the sense that the inner product of any two of them, taken entry by entry, is zero. And their norms are decreasing, and they are the singular values of the k-th unfolding.

That is called all-orthogonality, and it is the honest generalisation of the middle factor is diagonal: for a matrix, the slices perpendicular to either mode are single rows or columns of a diagonal matrix, and two of them are orthogonal for the trivial reason that their supports are disjoint. For a tensor the supports are not disjoint and the orthogonality is a real statement.

It is checked here rather than cited. The largest inner product between two slices of a core, relative to the core’s own energy, is below 10⁻⁹ on every family measured.

One detail of that measurement is worth a sentence because getting it wrong makes the property look false. The inner product between two slices has to be scaled by the core’s norm rather than by the two slices’ own norms. A core with a decaying spectrum has trailing slices at the rounding level, and the cosine between two vectors of norm 10⁻¹⁶ is a cosine between two roundings — O(1), and meaningless. The first version of this measurement reported a worst pair of 7·10⁻⁴ for exactly that reason.

What does not: diagonality #

A core is not diagonal, and the question worth asking is not whether but by how much.

Take the leading r × r × r block of the core and ask what fraction of the tensor’s energy sits on its superdiagonal — the r entries with all three indices equal. Everything else would have to be discarded by a decomposition that insisted on a diagonal middle.

The smooth families put most of their energy on the diagonal and still pay a factor of 20,000 in error for the last few per cent of it. The wave family — which is exactly multilinear rank two, and which the full core reproduces to the rounding level — puts a quarter of its energy there, so a diagonal reading of a tensor the format handles perfectly loses 86 per cent of it.

The last row is the one that settles the general question. A tensor with independent normal entries has 0.4 per cent of its energy on the superdiagonal of its own core, because there is no reason for it to have any — the same nothing-to-compress control the hierarchy field uses.

What a diagonal core would have to be #

It is worth writing down what is being asked for, because the request sounds modest until it is counted.

A decomposition with orthonormal factors and a diagonal core of length r says

T = Σⱼ σⱼ · uⱼ ⊗ vⱼ ⊗ wⱼ

with the u’s, the v’s and the w’s each orthonormal sets. Count the parameters. Each factor matrix is n × r with orthonormal columns, which is nr − r(r+1)/2 free numbers, and there are d of them, plus r singular values. For n = 12, d = 3 and r = 12 that is 3·(144 − 78) + 12 = 210.

A general 12 × 12 × 12 tensor has 1,728 numbers. So the set of tensors admitting such a decomposition has dimension 210 inside a space of dimension 1,728, which is a measure-zero subset of it — and a measure-zero subset is exactly what “almost no tensor has one” means.

For a matrix the same count gives 2·(144 − 78) + 12 = 144, and a 12 × 12 matrix has 144 numbers. The dimensions match, which is the counting version of the statement that every matrix has an SVD. There is nothing subtle in the difference: for d = 2 the parametrisation is exactly the right size and for d = 3 it is a fraction of the right size, and the fraction shrinks with d.

Two is the only dimension that fits, and it fits exactly #

The count above is done at one shape. Doing it at several turns an observation into a statement, and the statement is sharper than “the fraction shrinks with d”.

Take r = n, so the decomposition is asked to describe the whole tensor rather than an approximation. The parameters are d·(n² − n(n+1)/2) + n, which is d·n(n−1)/2 + n, and the space is n^d. At n = 12:

d = 1 gives 78 parameters for 12 numbers — 650 per cent, a redundant description, because an orthonormal basis plus a length is more than a vector needs. d = 2 gives 144 for 144. d = 3 gives 210 for 1,728, which is 12.2 per cent. d = 4 gives 276 for 20,736, or 1.3 per cent. d = 5 gives 0.137 per cent, and d = 6 gives 0.014 per cent.

The d = 2 row is not a near miss rounded to a whole number. It is an identity: n(n−1) + n = n², at every n, with nothing left over and nothing missing. That is the counting form of “every matrix has a singular value decomposition”, and writing it that way says something the theorem’s usual statement hides — the theorem is a dimensional coincidence. Two is exactly the number of index sets for which an orthonormal basis per index, plus one number per direction, is neither too much information nor too little.

And the failure above it is not marginal and does not narrow. The parametrisation grows linearly in d — one more orthonormal factor per index — while the space grows exponentially. So the shortfall widens by about a factor of n² per added index, and by six indices the set of tensors with an orthogonal diagonalisation is a fourteen-thousandth of one per cent of the space it sits in.

That places this essay’s finding rather than merely stating it. The failure of the SVD to generalise is not a separate awkwardness of three-index arrays, to be filed beside the rank being field-dependent and the best approximation not existing. It is the curse of dimensionality again, arriving in the parametrisation rather than in the storage: the same n^d against d·n that makes a Kronecker representation worth having makes an orthogonal diagonalisation impossible, and the two are the same arithmetic read in opposite directions.

It also explains why the repair the next essays take is the one it is. Giving up diagonality keeps the factors and pays r^d for the core — an exponential middle, which is the space’s own growth rate, so the count can match. Giving up orthogonality keeps a diagonal middle of length r and pays with factors that are no longer a basis. Both repairs restore the missing exponential somewhere, because the shortfall is exponential and nothing linear closes it.

The two decompositions, and what each gives up #

Naming the alternatives makes the trade explicit, because both exist and each keeps one of the two properties.

Keep orthogonality, give up diagonality. That is the higher-order SVD: orthonormal factors, all-orthogonal core, and r^d numbers in the middle. Its truncation is quasi-optimal, its cost is d matrix decompositions, and the previous essay measures both.

Keep diagonality, give up orthogonality. That is the CP decomposition: a sum of r rank-one terms, which is a diagonal core of size r, and factor matrices that are not orthogonal and generally cannot be. Its rank is the object the first two essays of this field are about — the one whose best approximation need not exist and whose value depends on the field.

There is no third option that keeps both, and the reason is a counting argument rather than an accident. An orthogonal decomposition with a diagonal core of size r has r(n₁ + n₂ + n₃ − 2) parameters after the orthogonality constraints are imposed, and a general tensor has n₁n₂n₃; the first is far smaller than the second for any r that keeps the factors orthonormal, so almost no tensor has one.

One caveat on the diagonal-energy table, because it measures a weaker thing than it appears to. The “error of a diagonal core” column is what happens when the off-diagonal entries of the higher-order SVD’s core are set to zero. That is not the best orthogonal decomposition with a diagonal core — it is the best one whose factors are the HOSVD’s, and nothing says those factors are the ones that concentrate the most energy on the diagonal. A rotation of each factor matrix that maximised the diagonal energy would do at least as well and generally better.

So the table’s numbers are an upper bound on the error of the diagonal reading rather than the error itself, and the honest form of the finding is that even the best-placed diagonal loses everything the counting argument says it must. The parameter count is what settles the general question, because it holds for every choice of orthonormal factors at once: 210 numbers cannot describe 1,728, however well they are chosen. The measured table says how bad the natural choice is; the count says that no choice is good.

That distinction matters for one family in particular. The wave family is exactly multilinear rank two — the full core reproduces it to 1.3·10⁻¹⁵ — and its diagonal reading loses 86 per cent. A reader could reasonably wonder whether a better rotation would recover it. The count says it cannot: a tensor the format handles perfectly is still, with probability one, outside the measure-zero set that has an orthogonal diagonalisation, and being easy for one decomposition says nothing about membership of the other’s domain.

Which property a computation actually needs #

The trade is only interesting because different uses want different halves, and it is worth going through the uses this collection has.

Compression wants orthogonality. A projection onto orthonormal factors has an error that is computable from the discarded singular values, and the bounds of the previous essay are made of them. A non-orthogonal factorisation has no such accounting: its error is whatever the fit achieved.

Interpretation wants diagonality. A rank-one term is a component, and a component is only a component if it stands alone. A core with entries off the diagonal says that direction three of mode one interacts with direction two of mode two, which is a true statement about the tensor and an unusable one about the data.

Arithmetic inside the format wants orthogonality. Adding two representations, applying an operator, truncating the result — all of it is stable when the bases are orthonormal and none of it is when they are not, which is the same reason the orthogonality field exists at all.

So the answer to which decomposition is decided by what is being done, and the two are not competitors for a single job. Where they are competitors, the measurement above says the cost of insisting on diagonality is between a factor of twenty thousand and a factor of a hundred.

An ordering that is not a spectrum #

One further property comes across and one does not, and they are easy to confuse.

The core’s slice norms are ordered — the first slice perpendicular to mode k has the largest norm, the second the next largest, and so on — and those norms are the singular values of the k-th unfolding. So each mode has a spectrum, and the picture of a decaying sequence that every truncation argument on this site relies on is available.

What is not available is a single spectrum for the tensor. There are d of them, they are different lengths, and there is no canonical way to merge them: dropping the last direction of mode one and dropping the last direction of mode two remove different amounts of energy, and neither is comparable with the other except through the sum in squares that the bound uses.

The consequence is that the phrase the k-th singular value of a tensor names nothing, which is why the truncation is specified by a triple of ranks rather than by a single cut-off. Every figure in this field that draws a spectrum draws d of them for that reason.

The matrix case, reconsidered #

It is worth going back and asking what the matrix case is actually doing, because the answer is not that matrices are better behaved.

A matrix has two modes. Its core, in the language above, is r × r, and all-orthogonality of an r × r core forces it to be diagonal: the slices perpendicular to mode one are its rows, the slices perpendicular to mode two are its columns, and requiring all pairs of rows and all pairs of columns to be orthogonal leaves only diagonal matrices.

So diagonality is not an extra property the SVD provides. It is a consequence of all-orthogonality, available only when d = 2, and it disappears the moment there are three sets of slices to be mutually orthogonal rather than two.

That is the cleanest statement of what this field’s break actually is. Nothing was lost; a coincidence stopped applying. And the coincidence is the reason every decomposition anyone learns first has both properties without either being requested.

The bound is quasi-optimal rather than optimal — it permits a factor of √d worse than the best possible rank-r approximation — and how much of that permission the truncation actually uses is a different question at every family.

The two compressible families spend essentially all of it. The next two do not, and the reason is that a truncation which is going to be badly wrong anyway does not need the whole of its allowance:

Those two are the extremes, and the third case sits between them without being between them in compressibility.

The bound is essentially attained where the truncation works and slack where it does not. 0.99998 and 0.99981 on the two compressible families is the √d factor being spent in full — the quasi-optimal bound is not a loose theoretical courtesy on these tensors, it is what happens. On the two incompressible ones the truncation comes in under its own permission, at 0.93 and 0.78.

Which is worth knowing because it inverts the usual reading of a quasi-optimality result. A factor of √d sounds like slack a practitioner can ignore; on the tensors anybody would actually truncate, it is the whole of the error’s excess over optimal.

The √d in the bound is measured rather than quoted: 1.7320 at d = 3 and 2.0000 at d = 4, against √3 = 1.73205 and √4 = 2. It is worth having as a measurement because the factor is the one number separating a Tucker truncation from the matrix SVD’s exact optimality, and because a constant typed into a figure rather than derived from its own d is a constant that stops being true the moment the dimension moves.

What it means for the rest of the collection #

Two arguments elsewhere on this site are quietly the same argument as this one, and putting them beside it is worth doing because none of the three is about tensors.

The hierarchy field’s recompression essay finds that a sum of two rank-k blocks is a rank-2k block exactly, so a format built on rank-k blocks is not closed under its own addition and every operation must be followed by a truncation. That is the same shape: the representation has a property the arithmetic does not preserve, and what is preserved instead is a bound on how much is lost.

The least-squares field’s normal equations essay finds that a route which is algebraically identical squares the condition number. Again the same shape: two constructions agree on what they compute and differ on what they preserve.

And the orthogonality field’s two Gram–Schmidts is the original. Same algebra, different arithmetic, and the difference is measured as ‖QᵀQ − I‖ rather than as a residual, because the residual does not see it.

What this page adds to the family is that the property being lost is not lost to rounding. Every measurement here is exact to the rounding level; the core is genuinely not diagonal, in exact arithmetic, for reasons of dimension. That makes it the cleanest member of the group: nothing about precision, nothing about an implementation, and a fact that survives being computed in any arithmetic at all.

The refusal #

The claim under test is the name. This decomposition is called the higher-order SVD, and the natural reading of that name is that its core plays the role a matrix’s middle factor plays.

So the assertion that the off-diagonal share of a smooth tensor’s core is below 10⁻⁸ is fed the measured value. It fails — the share is 2.3 per cent on the family where it is smallest, and 99.6 per cent on the family with no structure.

Refusing it matters because the name is the whole of the mistake. Nothing in the construction claims diagonality and nothing in the theorem claims it; what claims it is the analogy the name invites, and an analogy is not a thing a gate can fail. Feeding the assertion the number is the only available way to make the claim testable at all.

The file’s other refusals guard the two neighbouring readings. One is fed a rank-two truncation of a noise tensor and required to refuse the claim that it is exact — the untruncated decomposition is, and a truncation of it is not. The other is fed the ratio of the truncation error to the lower bound and required to refuse the claim that the projection attains it, which is the previous essay’s subject.