Numerical Linear Algebra
where the algebra stops being the arithmetic
When the index is a tuple

A rank that is not a property of the tensor

The same eight real numbers have rank three over the reals and rank two over the complexes, and a random 2 × 2 × 2 tensor has rank two with probability exactly π/4. Neither sentence has an analogue for matrices, where the rank is one number and a random matrix has the largest one.
34 min read 27 figures Where the algebra stops being the arithmeticExact ground truthMeasured, not asserted

Worth reading first: A nearest point that is not there · A block nobody can call sparse.

The rank of a real matrix is the same number whether its entries are read as real, complex, rational or anything else containing them. That is so standard it is difficult to state as a fact rather than as a definition: rank is the dimension of the column space, and extending the field does not add columns.

For three indices it is false. The same eight real numbers have rank three over the reals and rank two over the complexes.

The share of random 2 × 2 × 2 tensors with real rank two, against the number drawn, and π/4Each draw is eight independent standard normal entries and its rank is decided exactly, by the sign of the hyperdeterminant, with no iteration involved. Over 19,953 draws 15,705 have rank two — a share of 0.7871 against the exact value π/4 = 0.7854, inside 0.6 standard errors. The band is ±2 of them. A random matrix has one typical rank; this is the picture of a random object having two, each with a probability that is a number rather than an experiment.10¹10²10³10⁴00.050.10.150.20.250.30.350.40.450.50.550.60.650.70.750.80.850.90.951drawsshare with real rank twoπ/4 = 0.78539815,705 of 19,953 have rank twoa probability with a closed formdraws2·10⁴rank two1.6·10⁴share0.79π/40.79standard errors out0.59two typical ranksand the split is π/4
Fig. 1 And the other half of the same news: how often each real rank happens, over twenty thousand random tensors, against a closed form.

The classification, which is exact

The previous essay introduced the machinery and it is worth restating, because everything on this page runs on it and none of it is an iteration.

A 2 × 2 × 2 array has two 2 × 2 slices A₀ and A₁. The determinant of the pencil A₀ + λA₁ is a quadratic in λ, and its discriminant Δ = c₁² − 4c₀c₂ is Cayley’s hyperdeterminant. The sign of Δ decides the rank: positive gives two distinct real roots and a real rank of two; negative gives a conjugate pair and a real rank of three; zero gives a repeated root and, for a tensor whose unfoldings are all rank two, a real rank of three with the infimum over rank two equal to zero.

Every rank on this page is therefore a sign, computed from eight numbers by four multiplications and a subtraction. No decomposition is taken, no tolerance is chosen, and nothing converges. That is the property that makes the experiment below an experiment rather than an illustration.

A plane of 2 × 2 × 2 tensors, coloured by the sign of the hyperdeterminant that decides their rankTwo of the eight entries are varied over ±2 and the other six are held at the values that make the centre of the picture the rank-three tensor A = e₁⊗e₁⊗e₂ + e₁⊗e₂⊗e₁ + e₂⊗e₁⊗e₁. The light region is Δ > 0, where the tensor has real rank two and two real rank-one terms exist; the dark region is Δ < 0, where the real rank is three and the complex rank is two. 54.2 per cent of this window is rank two. The boundary between them is the curve Δ = 0, on which the rank is three and the distance to the rank-two set is zero — every point of it is a tensor with no nearest rank-two approximation.rank three, Δ = 0a₁₁₁ across, a₀₀₀ up, both over ±2light: two real roots, rank two · dark: a conjugate pair, rank threeone sign, two rankscells sampled4096rank two2222rank three1874Δ at the centre0rank at the centre3the rank is a signcomputed from eight numbers
Fig. 2 The sign, drawn over a plane of tensors. Two regions and a boundary, all of it decided by a polynomial in the entries.

The same numbers, two ranks

Take the tensor whose entries, in the order (i, j, k) with k fastest, are

1, 0, 0, 1, 0, −1, 1, 0

Its slices are A₀ = [[1, 0], [0, 1]] and A₁ = [[0, 1], [−1, 0]], so det(A₀ + λA₁) = 1 + λ², whose discriminant is −4. Δ < 0: the pencil’s roots are ±i, and the real rank is three.

Over the complexes the same pencil has two distinct roots, so the same construction that produces two real rank-one terms when Δ > 0 produces two complex rank-one terms here. They are conjugates of one another, so their sum is real — and the sum is the tensor, exactly.

The measurement is what makes that more than a citation. The complex decomposition is formed, the reconstruction is computed in complex arithmetic, and two numbers are reported: the residual against the original, and the imaginary part of the reconstruction. Both are zero to the rounding level. Two complex rank-one terms reproduce a real tensor with an imaginary part of 10⁻¹⁶, and no two real rank-one terms do.

So the sentence this tensor has rank two is incomplete in a way that has no matrix analogue. It needs a field, and the answer changes with it.

The three unfoldings of a 10 × 11 × 12 wave tensor, and the singular values of eachA tensor has one matrix per index — put that index on the rows and every other index down the columns — and each of those matrices has an ordinary rank. Here they are 2, 2, 2 at a relative tolerance of 10⁻⁸, from a tensor of 1320 entries whose modes are of different lengths. Nothing requires the three numbers to agree, and nothing requires any of them to be the tensor's own rank: they are three different matrices built from one array. The leading singular values are 18.7, 19.3, 18.7, each normalised to its own mode below.02468101210⁻¹⁶10⁻¹²10⁻⁸10⁻⁴1index of the singular valueσ ⁄ σ₁the tolerance the ranks are read atmode 1 · rank 2mode 2 · rank 2mode 3 · rank 2wave: three matrices, one arrayentries1320mode-1 rank2mode-2 rank2mode-3 rank2‖T‖26three ranksand none of them is the tensor's
Fig. 3 What the unfoldings say about the same question, which is nothing: every unfolding of a real tensor has the same rank over ℝ and over ℂ, because that part is ordinary matrix rank.

Why the matrix case does not do this

The reason is worth having explicitly, because it explains which other statements survive.

A matrix of rank r has an r-dimensional column space, and the field the entries are read over does not change how many linearly independent columns there are: a real matrix with r independent real columns has r independent complex columns, and vice versa by taking real and imaginary parts. Rank is the dimension of a subspace spanned by objects that are already in the matrix.

A tensor’s rank is not the dimension of anything inside the tensor. It is the least number of terms in a representation, and the terms are not required to lie in any space the tensor determines. Enlarging the field enlarges the supply of terms, and the supply is the whole question.

That also says which statements are safe. Anything about the unfoldings is field-independent, because unfolding ranks are matrix ranks. Anything about the multilinear rank — the triple of unfolding ranks — is safe. What is not safe is anything about the number of rank-one terms.

A plane of 2 × 2 × 2 tensors, coloured by the sign of the hyperdeterminant that decides their rankTwo of the eight entries are varied over ±6 and the other six are held at the values that make the centre of the picture the rank-three tensor A = e₁⊗e₁⊗e₂ + e₁⊗e₂⊗e₁ + e₂⊗e₁⊗e₁. The light region is Δ > 0, where the tensor has real rank two and two real rank-one terms exist; the dark region is Δ < 0, where the real rank is three and the complex rank is two. 87.2 per cent of this window is rank two. The boundary between them is the curve Δ = 0, on which the rank is three and the distance to the rank-two set is zero — every point of it is a tensor with no nearest rank-two approximation.rank three, Δ = 0a₁₁₁ across, a₀₀₀ up, both over ±6light: two real roots, rank two · dark: a conjugate pair, rank threeone sign, two rankscells sampled4096rank two3572rank three524Δ at the centre0rank at the centre3the rank is a signcomputed from eight numbers
Fig. 4 The widest window of the plane. The dark region is precisely the set of real tensors whose complex rank is smaller than their real rank, which over ℂ would be no region at all.

What it costs to check

The complex decomposition above needs complex arithmetic, which this collection does not otherwise have: every routine in matrix.js is real, deliberately, because every argument the site makes about rounding is easier to read in real arithmetic and none of them needed the extension.

So the construction here is written out rather than called. Two 2 × 2 complex systems are solved by elimination, with complex multiplication and division spelled out as pairs of reals, and the whole thing is thirty lines. That is worth doing rather than avoiding for the reason the site’s own libraries exist: what the essay argues about is the decomposition, and a decomposition performed by a library is a decomposition nobody has read.

The check that it is right is the same two-route habit as everywhere else. The complex factors are formed from the pencil’s eigenvector, the reconstruction is computed entry by entry from them, and the result is compared against the eight numbers it started from. It agrees to 10⁻¹⁶, and its imaginary part is 10⁻¹⁶ separately — two numbers rather than one, because a reconstruction that happened to be real and wrong would pass a residual test on the real part alone.

The spectrum in the plane, with the pair at 1 ± 2.00iA complex plane with the real axis marked. Open circles show the eigenvalues the matrix was built from and filled dots show the ones the algorithm returned; two of them sit symmetrically above and below the real axis.-5-3-1135-202real partimaginary partbuilt incomputedthe real line — where a real shift lives‖A − ZTZᵀ‖/‖A‖4.1·10⁻¹⁵‖ZᵀZ − I‖4.2·10⁻¹⁵worst eigenvalue error1.1·10⁻¹⁴departure from normality10⁻¹⁸5×5 real matrix, 1 conjugate pairthe answer is not on the axis
Fig. 5 The spectra field’s picture of a conjugate pair, from the essay that keeps a real matrix real: the same algebra, in the field this site does its arithmetic in.
The real Schur form with 2 conjugate pairs: 2 blocks that cannot be splitA square matrix drawn as a grid. Everything below the diagonal is zero except for a small number of two-by-two boxes on the diagonal, which are highlighted.3000000120000-21000000-0.5-1.500001.5-0.5000000-2T = ZᵀAZthe highlighted boxes each hold one conjugate pair, and no real rotation removes themthe form, and that it is one‖A − ZTZᵀ‖/‖A‖1.8·10⁻¹⁵‖ZᵀZ − I‖2.5·10⁻¹⁵worst eigenvalue error2.7·10⁻¹⁵surviving subdiagonal26×6, spectrum chosen before the matrix was builtquasi-triangular is as far as the reals go
Fig. 6 And the form that avoids complex arithmetic entirely for the eigenvalue problem — the option that is not available here, because the two complex terms do not combine into one real block.

Two typical ranks, and one of them has a probability

The second half of the page is stranger than the first, and it is measurable to four digits.

Draw a matrix with independent standard normal entries. Its rank is the largest possible, with probability one; the set of lower-rank matrices is a measure-zero variety, and nothing else happens. All of this collection’s talk of numerical rank is about matrices near that set rather than on it.

Draw a 2 × 2 × 2 tensor with independent standard normal entries. Its rank is two with probability π/4 and three with probability 1 − π/4. Both sets have positive measure. There is no such thing as the typical rank of a real 2 × 2 × 2 tensor; there are two of them.

The hero figure is that statement, run. Twenty thousand draws, each classified exactly by the sign of Δ, with the running share plotted against the number drawn and a two-standard-error band around π/4. The measured share lands inside the band and within about one standard error of 0.785398.

That is exact-ground-truth applied to a statement about a random object, which is a combination this collection has had only once before — the randomised field’s bounds hold with a probability and are not equal to one. Here the probability itself is a closed form, so the experiment has a number to be wrong about.

The share of random 2 × 2 × 2 tensors with real rank two, against the number drawn, and π/4Each draw is eight independent standard normal entries and its rank is decided exactly, by the sign of the hyperdeterminant, with no iteration involved. Over 100 draws 73 have rank two — a share of 0.7300 against the exact value π/4 = 0.7854, inside 1.3 standard errors. The band is ±2 of them. A random matrix has one typical rank; this is the picture of a random object having two, each with a probability that is a number rather than an experiment.10¹10²00.050.10.150.20.250.30.350.40.450.50.550.60.650.70.750.80.850.90.951drawsshare with real rank twoπ/4 = 0.78539873 of 100 have rank twoa probability with a closed formdraws100rank two73share0.73π/40.79standard errors out1.3two typical ranksand the split is π/4
Fig. 7 A hundred draws, where the honest uncertainty is wide enough that π/4 and four fifths are indistinguishable — the reason the count on the horizontal axis is part of the claim.
The share of random 2 × 2 × 2 tensors with real rank two, against the number drawn, and π/4Each draw is eight independent standard normal entries and its rank is decided exactly, by the sign of the hyperdeterminant, with no iteration involved. Over 1,995 draws 1,589 have rank two — a share of 0.7965 against the exact value π/4 = 0.7854, inside 1.2 standard errors. The band is ±2 of them. A random matrix has one typical rank; this is the picture of a random object having two, each with a probability that is a number rather than an experiment.10¹10²10³00.050.10.150.20.250.30.350.40.450.50.550.60.650.70.750.80.850.90.951drawsshare with real rank twoπ/4 = 0.7853981,589 of 1,995 have rank twoa probability with a closed formdraws1995rank two1589share0.8π/40.79standard errors out1.2two typical ranksand the split is π/4
Fig. 8 Two thousand, where the band has narrowed by a factor of four and the curve has stopped wandering.

What a typical rank is for

The phrase is not decoration. It is what decides whether a modelling choice is well posed.

Fitting a rank-two model to 2 × 2 × 2 data is a reasonable thing to do about 78.5 per cent of the time and an ill-posed thing to do the rest of the time — not because the fit fails, but because the target’s own rank is three and the rank-two set does not contain a nearest point to it. The previous essay’s sequence is what an optimiser does in that case.

So the honest description of a rank-two CP fit to this shape of data is: with probability π/4 there is an exact answer, and with probability 1 − π/4 there is an infimum that is not attained. No amount of care in the algorithm changes which of those the data is, and the diagnostic is not the residual.

For larger shapes the same phenomenon occurs with different numbers, and the numbers are mostly not known in closed form. What is known is that real tensors generically have more than one typical rank whenever the shape is not too lopsided, and that the smallest of them is the generic rank over ℂ. So the complex answer is the single number, and the real answer is a list.

A rank-two sequence approaching a rank-three tensor: the residual falls like 1/n and the terms grow like nA_n = n(e₁ + e₂/n)⊗³ − n·e₁⊗³ has rank two for every n and converges to a tensor of rank three. The falling curve is ‖A_n − A‖, which is √(3/n² + 1/n⁴) exactly and reaches 0.00169 at n = 1024; the rising one is the norm of the larger of its two rank-one terms, 1024. Their product runs 2.519, 1.917, 1.777 … 1.73205, descending onto √3 = 1.73205. So getting one digit closer costs a factor of ten in the size of the pieces, for ever, and the infimum of the distance is zero while no rank-two tensor attains it.110¹10²10³10⁻³10⁻²10⁻¹110¹10²10³n‖A_n − A‖ and the largest term's norm‖A_n − A‖the larger of its two termsan infimum that is not attainedn1024‖A_n − A‖0.0017largest term1024their product1.7√31.7the distance goes to zeroand nothing reaches it
Fig. 9 What the second case looks like: the sequence from the previous essay, which is what the 21.5 per cent of draws is measured against.
Alternating least squares on a tensor with a rank-two answer and on one without, over 20,000 sweepsThe steeply falling curve is a rank-three fit to a tensor built from rank-three factors: it reaches 9.74·10⁻¹⁵ in 58 sweeps and its largest term does not move — 12.202 at sweep twenty and 12.202 at the end. The other is a rank-two fit to the border-rank tensor, whose error goes from 0.00677 to 0.00141 and has not finished, while the rising curve is its largest term: 4.698 to 10.15, a factor of 2.16. Fitted over 199 points, the error falls as the 2.03 power of the term size — a better path than the explicit sequence's 1/n, and still one that leaves the set rather than converging inside it.110¹10²10³10⁴10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹sweeprelative error, and the largest term's sizerising: the swamp's largest rank-one termfalling, slowly: its errorfalling, once: a fit with an answera plateau with a rising floorswamp error0.0014swamp term10term growth2.2benign error9.7·10⁻¹⁵benign term growth1the error alone cannot tellthe size of the terms can
Fig. 10 And what an optimiser does with it, from four essays on.

The three quantities, kept apart

This field now has three numbers all called rank and it is worth putting them side by side, because every confusion in it is a confusion between two of them.

Rank is the least number of rank-one terms whose sum is the tensor, over a stated field. It is field-dependent, it is NP-hard to compute in general, and the set of tensors with rank at most r is not closed.

Border rank is the least r such that the tensor is a limit of rank-r tensors. It is what a truncation approaches and it is what a numerical rank at a tolerance actually reports.

Multilinear rank is the triple of unfolding ranks. It is field-independent, computable by three matrix decompositions, and the set of tensors with multilinear rank at most (r₁, r₂, r₃) is closed — which is why the next two essays are about it and not about the first two.

A matrix collapses all three into one number, which is why none of these distinctions has appeared anywhere else on this site.

The three unfoldings of a 10 × 11 × 12 smooth tensor, and the singular values of eachA tensor has one matrix per index — put that index on the rows and every other index down the columns — and each of those matrices has an ordinary rank. Here they are 8, 8, 8 at a relative tolerance of 10⁻⁸, from a tensor of 1320 entries whose modes are of different lengths. Nothing requires the three numbers to agree, and nothing requires any of them to be the tensor's own rank: they are three different matrices built from one array. The leading singular values are 2.37, 2.37, 2.37, each normalised to its own mode below.02468101210⁻¹⁶10⁻¹²10⁻⁸10⁻⁴1index of the singular valueσ ⁄ σ₁the tolerance the ranks are read atmode 1 · rank 8mode 2 · rank 8mode 3 · rank 8smooth: three matrices, one arrayentries1320mode-1 rank8mode-2 rank8mode-3 rank8‖T‖2.4three ranksand none of them is the tensor's
Fig. 11 The third of the three, on a smooth array: three ordinary matrix ranks that are close and are not equal, and neither of the other two quantities is visible on the picture.
The truncation error of a hilbert tensor against the rank kept, between the two bounds the theorem givesThe middle curve is the measured error of the projection; the upper dashed one is √(Σ_k tail_k²), which the theorem says it cannot exceed, and the lower one is max_k tail_k, which the best possible error cannot fall below. They are a factor of √3 apart. The measurement is that the projection sits on the upper one, and not between them: the ratio of error to bound runs 0.689, 0.829, 0.906, 0.950 … 0.999812, so by rank 10 the bound is attained to five decimals and the ratio to the lower bound is 1.7317 against √3 = 1.7321. That reads as a bad result and is not one — what it says is that the lower bound is weak, which only a second measurement can establish.024681010⁻¹²10⁻⁹10⁻⁶10⁻³1rank kept in every moderelative errordashes above: √(Σ tail²), the upper bounddashes below: max tail, a floor under the bestsolid: what the projection returnshilbert: pinned to the upper boundrank 10 error1.4·10⁻¹²its upper bound1.4·10⁻¹²the lower bound8.3·10⁻¹³error ⁄ bound1error ⁄ lower1.7inside the boundand sitting on it
Fig. 12 And what the third one is worth: a truncation with a bound either side of it, on a set that contains its own limit points.

Where the closed form comes from

The π/4 is not a fitted constant and it is worth saying where it comes from, because a reader shown a measurement against a transcendental number is entitled to ask whether the number was chosen after the experiment.

Δ is a quartic form in the eight entries. The share of Gaussian tensors with Δ > 0 is therefore the proportion of the sphere in eight dimensions on which that form is positive, and for this particular quartic the proportion evaluates in closed form. The derivation is not this site’s to reproduce; what this site can do is what it does with every other claimed constant — compute the quantity a different way and see whether the two agree.

The different way is the experiment on the hero figure, and the agreement is to within about one standard error at twenty thousand draws. That is the same discipline as the arithmetic field’s check that a simulated 24-bit rounding equals the hardware’s Math.fround: a route that could have disagreed, and did not.

The share of random 2 × 2 × 2 tensors with real rank two, against the number drawn, and π/4Each draw is eight independent standard normal entries and its rank is decided exactly, by the sign of the hyperdeterminant, with no iteration involved. Over 50,119 draws 39,500 have rank two — a share of 0.7881 against the exact value π/4 = 0.7854, inside 1.5 standard errors. The band is ±2 of them. A random matrix has one typical rank; this is the picture of a random object having two, each with a probability that is a number rather than an experiment.10¹10²10³10⁴00.050.10.150.20.250.30.350.40.450.50.550.60.650.70.750.80.850.90.951drawsshare with real rank twoπ/4 = 0.78539839,500 of 50,119 have rank twoa probability with a closed formdraws5·10⁴rank two4·10⁴share0.79π/40.79standard errors out1.5two typical ranksand the split is π/4
Fig. 13 The longest run the figure is drawn at — fifty thousand draws, where the band is narrow enough that a constant differing from π/4 in the third decimal would be visible.

A note on the arithmetic

Every measurement on this page is a sign, so the usual worry — that a rank verdict is really a verdict about a tolerance — does not apply in the usual way. It applies in a different way and the code says so.

Δ is a polynomial in the entries, so its sign is exact except where the entries make it small, and the classification here divides Δ by the fourth power of the tensor’s norm before comparing it against a tolerance. That scaling is not cosmetic: Δ has degree four, so doubling every entry multiplies it by sixteen, and a threshold on Δ itself would be a threshold that moves with the units the data is measured in — which is the failure this collection has a whole essay about.

The tolerance still matters for the Δ = 0 boundary, which has measure zero and is therefore never hit by a random draw and always hit by a constructed example. The tensors in the previous essay are exactly there, which is why they are constructed rather than sampled.

Two condition numbers of one 8×8 system, as its rows are put into different unitsFour curves against the spread of the row units, in decades. κ_∞ of the scaled matrix rises from 9.83 to 1.9·10⁸ while the componentwise condition number stays at 6.98 throughout — the same system, the same solution, and one of the two numbers is a fact about the units. Hilbert's two numbers are drawn flat beside them at 3.4·10¹⁰ and 1.2·10¹⁰: a matrix whose sensitivity no scaling repairs.02468110²10⁴10⁶10⁸10¹⁰10¹²spread of the row units (decades)condition numberκ_∞(DA)cond(DA)Hilbert κ_∞Hilbert condone system, two numbersκ_∞ at no spread9.8κ_∞ at 8 decades1.9·10⁸cond, either end7Hilbert, equilibrated1.3·10¹⁰the solution is the same at every spreadand one of these curves knows it
Fig. 14 The failure the scaling avoids, from the error field: a quantity compared against a fixed threshold when its units are a choice.
Two perturbation bounds and the error that was measured, on a 8×8 matrix spread over 6 decades of unitsThree curves against the size of an entrywise relative perturbation. The normwise bound κ_∞·ε is a valid bound and sits 4·10⁵ times above the componentwise one cond(A, x)·ε, which is also a bound and is nearly attained by the worst of forty random perturbations at each size.10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³relative size of the entrywise perturbationrelative forward errorκ_∞ · εcond(A,x) · εmeasuredboth bounds holdκ_∞(A)1.9·10⁶cond(A, x)4.8ratio of the bounds4·10⁵both curves above the data are boundsand only one of them is a measurement
Fig. 15 And the sharper version of the same rule, from the essay that measures it.

The refusal

The claim under test is the one a reader is most likely to leave with after being told that two ranks occur: that the two are somehow symmetric, or equally likely, or that the split is a detail of the particular experiment.

Four thousand draws are classified and the assertion that the share is a half within two per cent is fed the result. It fails, at 0.786 against 0.5, by ninety-five standard errors.

That the split is π/4 rather than a half is the whole content of the second half of this page. A phenomenon that happened half the time would be a symmetry; one that happens 78.5 per cent of the time is a measurement of a specific geometric fact — the relative volume of the two components of the real rank-two locus — and it is a number that an experiment can be right or wrong about.

The other two refusals in the same file guard the first half. One is fed an ordinary rank-two tensor and required to refuse the claim that it has rank three, which is what keeps the phenomenon from being a statement about every tensor. The other is fed the Δ < 0 tensor and required to refuse the claim that the largest unfolding rank is the tensor’s rank — which is the reading that most nearly works, since it gives the right answer whenever the two happen to coincide.

At other settings

The share of random 2 × 2 × 2 tensors with real rank two, against the number drawn, and π/4Each draw is eight independent standard normal entries and its rank is decided exactly, by the sign of the hyperdeterminant, with no iteration involved. Over 10,000 draws 7,865 have rank two — a share of 0.7865 against the exact value π/4 = 0.7854, inside 0.3 standard errors. The band is ±2 of them. A random matrix has one typical rank; this is the picture of a random object having two, each with a probability that is a number rather than an experiment.10¹10²10³10⁴00.050.10.150.20.250.30.350.40.450.50.550.60.650.70.750.80.850.90.951drawsshare with real rank twoπ/4 = 0.7853987,865 of 10,000 have rank twoa probability with a closed formdraws10⁴rank two7865share0.79π/40.79standard errors out0.27two typical ranksand the split is π/4
Fig. 16 Ten thousand draws, for reading against the hero’s twenty thousand: the band narrows by √2 and the verdict does not change.
The share of random 2 × 2 × 2 tensors with real rank two, against the number drawn, and π/4Each draw is eight independent standard normal entries and its rank is decided exactly, by the sign of the hyperdeterminant, with no iteration involved. Over 501 draws 392 have rank two — a share of 0.7824 against the exact value π/4 = 0.7854, inside 0.2 standard errors. The band is ±2 of them. A random matrix has one typical rank; this is the picture of a random object having two, each with a probability that is a number rather than an experiment.10¹10²00.050.10.150.20.250.30.350.40.450.50.550.60.650.70.750.80.850.90.951drawsshare with real rank twoπ/4 = 0.785398392 of 501 have rank twoa probability with a closed formdraws501rank two392share0.78π/40.79standard errors out0.16two typical ranksand the split is π/4
Fig. 17 Five hundred, which is about where the experiment first separates π/4 from four fifths.
A plane of 2 × 2 × 2 tensors, coloured by the sign of the hyperdeterminant that decides their rankTwo of the eight entries are varied over ±0.5 and the other six are held at the values that make the centre of the picture the rank-three tensor A = e₁⊗e₁⊗e₂ + e₁⊗e₂⊗e₁ + e₂⊗e₁⊗e₁. The light region is Δ > 0, where the tensor has real rank two and two real rank-one terms exist; the dark region is Δ < 0, where the real rank is three and the complex rank is two. 50.0 per cent of this window is rank two. The boundary between them is the curve Δ = 0, on which the rank is three and the distance to the rank-two set is zero — every point of it is a tensor with no nearest rank-two approximation.rank three, Δ = 0a₁₁₁ across, a₀₀₀ up, both over ±0.5light: two real roots, rank two · dark: a conjugate pair, rank threeone sign, two rankscells sampled4096rank two2048rank three2048Δ at the centre0rank at the centre3the rank is a signcomputed from eight numbers
Fig. 18 The plane at four times the magnification, where the boundary between the two ranks is a curve rather than a wedge.
A plane of 2 × 2 × 2 tensors, coloured by the sign of the hyperdeterminant that decides their rankTwo of the eight entries are varied over ±1 and the other six are held at the values that make the centre of the picture the rank-three tensor A = e₁⊗e₁⊗e₂ + e₁⊗e₂⊗e₁ + e₂⊗e₁⊗e₁. The light region is Δ > 0, where the tensor has real rank two and two real rank-one terms exist; the dark region is Δ < 0, where the real rank is three and the complex rank is two. 50.0 per cent of this window is rank two. The boundary between them is the curve Δ = 0, on which the rank is three and the distance to the rank-two set is zero — every point of it is a tensor with no nearest rank-two approximation.rank three, Δ = 0a₁₁₁ across, a₀₀₀ up, both over ±1light: two real roots, rank two · dark: a conjugate pair, rank threeone sign, two rankscells sampled4096rank two2048rank three2048Δ at the centre0rank at the centre3the rank is a signcomputed from eight numbers
Fig. 19 And the intermediate window, for reading against the other three.
A rank-two sequence approaching a rank-three tensor: the residual falls like 1/n and the terms grow like nA_n = n(e₁ + e₂/n)⊗³ − n·e₁⊗³ has rank two for every n and converges to a tensor of rank three. The falling curve is ‖A_n − A‖, which is √(3/n² + 1/n⁴) exactly and reaches 2.64·10⁻⁵ at n = 65536; the rising one is the norm of the larger of its two rank-one terms, 65540. Their product runs 2.519, 1.917, 1.777 … 1.73205, descending onto √3 = 1.73205. So getting one digit closer costs a factor of ten in the size of the pieces, for ever, and the infimum of the distance is zero while no rank-two tensor attains it.110¹10²10³10⁴10⁻⁴10⁻³10⁻²10⁻¹110¹10²10³10⁴10⁵n‖A_n − A‖ and the largest term's norm‖A_n − A‖the larger of its two termsan infimum that is not attainedn6.6·10⁴‖A_n − A‖2.6·10⁻⁵largest term6.6·10⁴their product1.7√31.7the distance goes to zeroand nothing reaches it
Fig. 20 The measure-zero case, extended as far as the sequence is drawn.
The three unfoldings of a 10 × 11 × 12 noise tensor, and the singular values of eachA tensor has one matrix per index — put that index on the rows and every other index down the columns — and each of those matrices has an ordinary rank. Here they are 10, 11, 12 at a relative tolerance of 10⁻⁸, from a tensor of 1320 entries whose modes are of different lengths. Nothing requires the three numbers to agree, and nothing requires any of them to be the tensor's own rank: they are three different matrices built from one array. The leading singular values are 14.2, 13.6, 13.4, each normalised to its own mode below.02468101210⁻¹⁶10⁻¹²10⁻⁸10⁻⁴1index of the singular valueσ ⁄ σ₁the tolerance the ranks are read atmode 1 · rank 10mode 2 · rank 11mode 3 · rank 12noise: three matrices, one arrayentries1320mode-1 rank10mode-2 rank11mode-3 rank12‖T‖36three ranksand none of them is the tensor's
Fig. 21 An array with no structure, seen through its three unfoldings — all full, and none of them a rank in the sense this page is about.
The randomised SVD against the optimum it cannot beat, with 1 power iterationA semi-logarithmic plot of approximation error against target rank. A shaded band shows the spread across seeds, a solid line the optimal error from the exact singular values, and a dashed line the published probabilistic bound well above both.04812162010⁻¹10⁻⁰.⁵1target rank k‖A − A_k‖₂published boundrandomisedσ_{k+1}, optimalhow far apart the three areworst seed spread1.2bound / median at k = 1211median / optimum at k = 12160×60, 6 seeds, oversampling p = 5band is best to worst
Fig. 22 The randomised field’s version of a claim that holds with a probability, for comparison: a band rather than a line, and no closed form for where the band sits.
Sketch distortion against sketch width, for 40 vectorsA log-log plot of the worst relative change in vector length against the number of rows in the sketch, for vectors of two dimensions a factor of four apart. The two curves lie almost on top of one another and both fall steadily.10²10².³10².⁵⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁶10⁻¹10⁻⁰.⁵1rows in the sketchworst relative distortiondimension 64dimension 2565 seeds per point, band is best to worstthe dimension does not appear
Fig. 23 And the same field’s measurement of what a random object does to a norm, which is the other place on this site where a probability is the answer.
What a rank-10 approximation can achieve, by spectrumA semi-logarithmic plot of singular value against index for three spectra — geometric decay, algebraic decay, and flat — with the rank-ten approximation error marked on each.1112131415110⁻³10⁻²10⁻¹1index jσⱼσ11geometric, 0.85ʲalgebraic, j^−0.50flatmeasured, and equal to σ₁₁rank-10 error, geometric0.2rank-10 error, algebraic0.3rank-10 error, flat160×60, spectrum chosen rather than the entriesthe matrix decides, not the method
Fig. 24 A matrix spectrum with no gap in it, which is the matrix case’s nearest thing to a rank that is not a number.
Along a sequence of exactly rank-two tensors: the step's condition number, and what a fit from a random start achievesEvery A_n on this sequence *is* a rank-two tensor and its two rank-one terms are written down, so nothing here is about existence. The rising curve is the condition number of the r × r system each alternating sweep solves, which on this sequence has a closed form in n whose asymptote is 2n² — the marks are measured and the dashed line is that closed form, agreeing to 8·10⁻¹⁵. The lower marks are what a three-hundred-sweep fit from a random start returns: 2.1·10⁻⁴ at n = 2 rising to 0.0117 at n = 32. Started at the answer instead, the same code stays within 8.9·10⁻¹² of it at every n — not the rounding level, because the drift from an exact start is itself about κ times the unit roundoff, but nine orders below what a random start reaches. That is the control that says the failure is the conditioning and not the implementation. A tensor away from the boundary conditions its step at 6.03.110¹10⁻¹²10⁻⁹10⁻⁶10⁻³110³ncondition number, and residual reachedmarks above: κ of the step · dashes: its closed formmiddle: a fit from a random startbelow: the same fit started at the answera decomposition that is ill-conditionedκ at n = 322049its closed form2049cosine of the terms1from a random start0.012from the answer8.9·10⁻¹²the answer existsand cannot be found
Fig. 25 And what the Δ = 0 boundary costs a decomposition, from the error field.
The Kronecker spectrum of the inverse of a Kronecker sum on 8 points a sideA Kronecker product B ⊗ C, read as a four-index array and cut between its two index pairs, is exactly rank one. The inverse of T ⊕ T is rank 8 at the same cut, so the format is not closed under inversion — which is why a solve in it goes through the eigenbasis rather than through an inverse. What the spectrum says is that it is nearly closed: the singular values are 1, 0.19, 0.0262, 0.00214 of the first, and the number of Kronecker terms needed runs 3, 5, 6, 7, 8, 8 at 10⁻², 10⁻⁴, 10⁻⁶, 10⁻⁸, 10⁻¹⁰ and 10⁻¹². That is 0.50 terms a decade — the same shape, and nearly the same number, as the 0.554 columns a decade the hierarchy field measures for a kernel block, arrived at from a different direction entirely.024681012141610⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹index of the singular value at the cutσ ⁄ σ₁eight digits10^-4: 5 Kronecker terms10^-8: 7 Kronecker terms10^-12: 8 Kronecker termsnot closed, and nearly closedrank at the cut8a Kronecker product's1terms at 10⁻⁴5terms at 10⁻⁸7terms a decade0.5the inverse leaves the formatby half a term a decade
Fig. 26 A rank of a different kind from earlier in this field, for contrast: a Kronecker rank read off a cut of a four-index array, where the object being ranked is a matrix and the number means one thing.
The share of a HOSVD core's energy on its superdiagonal, by family, at rank 6A matrix SVD hands over orthonormal factors and a diagonal middle at the same time. For three indices they come apart, and this is the half that does not survive. Every core here is all-orthogonal — the largest inner product between two slices perpendicular to a mode, relative to the core's own energy, is 3.5·10⁻¹⁶ — and none of them is diagonal. The bars are the fraction of the squared norm carried by the 6 entries on the superdiagonal: smooth 97.7%, hilbert 94.5%, wave 26.6%, noise 0.4%. Keeping only those entries costs 0.152, 0.235, 0.857, 0.998 in relative error against the full core's 7.94·10⁻⁶, 1.77·10⁻⁶, 1.34·10⁻¹⁵, 0.842.smooth97.7%hilbert94.5%wave26.6%noise0.4%share of the core's energy on its 6 superdiagonal entrieskeeping only them: 0.152 against 7.94·10⁻⁶keeping only them: 0.235 against 1.77·10⁻⁶keeping only them: 0.857 against 1.34·10⁻¹⁵keeping only them: 0.998 against 0.842orthogonal, and not diagonalsmooth on-diagonal0.98hilbert on-diagonal0.94wave on-diagonal0.27noise on-diagonal0.0044worst slice pair3.5·10⁻¹⁶the slices are orthogonalthe core is not diagonal
Fig. 27 And what the third of the three quantities buys, from the next essay: a core whose slices are orthogonal, on a set that contains its own limit points.

Where this goes next

110¹10²10³10⁻³10⁻²10⁻¹110¹10²10³n‖A_n − A‖ and the largest term's norm‖A_n − A‖the larger of its two termsan infimum that is not attainedn1024‖A_n − A‖0.0017largest term1024their product1.7√31.7the distance goes to zeroand nothing reaches it A nearest point that is not there Eckart and Young guarantee that a matrix has a best rank-k approximation and that the truncated SVD is it. For three indices the guarantee is false in the strongest available way — there are tensors whose distance to the rank-two set is zero and which no rank-two tensor equals. 1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision Rank is a decision A floating-point matrix does not have a rank. It has a spectrum of singular values, and somewhere in that spectrum is a place where the values stop being signal and start being noise. Deciding where is a judgement, and the evidence for it is a gap. 04812162010⁻¹10⁻⁰.⁵1target rank k‖A − A_k‖₂published boundrandomisedσ_{k+1}, optimalhow far apart the three areworst seed spread1.6bound / median at k = 125.9median / optimum at k = 121.960×60, 6 seeds, oversampling p = 5band is best to worst A bound that holds with probability Every other guarantee on this site is deterministic. The randomised low-rank approximation offers one that holds with a probability, the seed changes the answer, and the honest figure is a band rather than a line.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Border rankEckart–YoungExact ground truthHyperdeterminantLow-rank approximationNumerical rankSeeded generatorTensor rankTypical rankUnfolding