Every essay — page 16
When the index is a tuple
A discretisation on a d-dimensional grid has n^d unknowns, so its matrix has n²ᵈ entries — a number with no physical meaning. What such a matrix usually is instead is a sum of d Kronecker products of n × n matrices, and nothing has been approximated: assembling it was the mistake. Then the same word is carried one step further, to arrays with three or more indices, and every theorem this site has relied on about rank stops being true. The best approximation may not exist, the rank depends on the field the entries are read over, and there is no decomposition that is orthogonal and diagonal at once. What survives is not the definition but the algorithm: take the SVDs of the reshapes, and existence, computability and a quasi-optimality factor all come back.
A decomposition made only of SVDs
Everything the definition of tensor rank loses comes back if the SVD's algorithm is carried across instead of its definition — take the leading left singular subspace of every unfolding and project onto all of them.
The orthogonality that cannot be diagonal
A matrix decomposition hands over orthonormal factors and a diagonal middle at once.
The format that does not notice the dimension
A Tucker core is r^d numbers, so the format that repaired the definition still cannot go past five indices.
An iteration that walks out of the set
Every sweep of alternating least squares is the exact minimiser of its own subproblem, so the objective can only fall.
A factorisation that is unique for once
A rank-r factorisation of a matrix is never unique — AB is (AM)(M⁻¹B) for any invertible M, so no factor means anything on its own.
A compression of 10¹⁴ that still does not fit
A Tucker core of a twenty-index array at rank four is 1.1·10¹² numbers against the tensor's 1.05·10²⁶ — a compression by a factor of 9.5·10¹³ that is still nearly nine terabytes.
Five indices are cheaper than two
The same 4,096 unknowns cost 1.049·10⁶ multiplications indexed as a 64 × 64 grid and 1.966·10⁵ indexed as six axes of four.
The digit that costs more than the tensor
Ask a three-index reciprocal tensor on six points a side for seven digits and its train is 288 numbers against 216 entries.
One term too many
A tensor built from three rank-one terms, fitted with four, reaches a relative error of 1.0·10⁻¹³ in seventy-six sweeps.
The repair that costs exactly itself
A ridge on every subproblem is the standard cure for a swamp and it works — the terms stop at 1.61 instead of climbing past 6.7, and a run that never finished finishes in 798 sweeps.
The test that is a deadline
The quantity that separates a boundary from slow convergence fires on every run that has nothing to reach, at sweep 21 of four thousand, and on no ordinary fit.
The rank a sweep can vouch for
To decide a tensor's rank, fit it at one rank after another and stop where something changes.
A fit that has an answer and cannot stop
Fit a noisy rank-three tensor with four terms and the prediction was that the spare term would find real structure in the noise and stop pairing off with the others.
A still error is not a settled one
A CP fit with one term too many on a noisy tensor never meets the usual stopping test, and its error has settled by sweep 150.
The rank that stops being typical
A random 2 × 2 × 2 tensor has rank two with probability π/4 and rank three otherwise, and the sentence has no analogue for matrices.
A fit with no answer to find
Half of all random 3 × 3 × 2 tensors, and most larger ones, have no rank-three decomposition, because their pencil has a complex pair.
A stop that knows the distance
A rank-two fit to a random 2 × 2 × 2 tensor of rank three settles at the tensor's distance to the boundary of the rank-two set while its terms grow without limit, and the distance can be computed without fitting.
Unique, and not determined
Kruskal's condition says a CP decomposition is unique, and it says it as a yes or a no.
The iteration pays the square
A rank-three tensor whose third factor has two columns at an angle θ is unique by Kruskal's condition at every angle above zero, and its decomposition moves by about 1/θ perturbations when the tensor is perturbed.
The penalty walks the same curve
A rank-two fit to a random 2 × 2 × 2 tensor of rank three has no best answer: its error falls towards the tensor's distance to the boundary along a law, d + C/s², while its terms grow without limit.
The matrix that is a graph
Every matrix in the fields before this one arrives as a matrix. A graph does not: it arrives as vertices and edges, two different matrices can be built from it that answer different questions, and what anybody wants back is a partition, a ranking or a count — a discrete answer, computed by continuous arithmetic. So a rounding here does not make the answer slightly wrong, it makes it a different answer: a connected graph reported as two pieces, a leaderboard whose middle places are decided by one uncrawled link, a determinant that is known in advance to be a whole number and stops being one at sixteen vertices while the elimination that produced it stays backward stable throughout. Two things this field has that nothing else on the site does. The Laplacian's null vector is exact — the rows are cancellations of integers, so L·1 is zero rather than nearly zero. And there is a two-sided bound that is proved rather than estimated, from one matrix–vector product.
A matrix with no numbers in it
A graph arrives as vertices and edges. Two different matrices can be built from it, they answer different questions, and one of them has a null vector that is exact — the only object in these essays whose kernel is known before anything runs.
Two Laplacians of one graph
The combinatorial Laplacian D − A and the normalised one, which conjugates it by the inverse square roots of the degrees, are built from the same object, are not similar to each other, and answer different questions.
The vertex nobody solves for
A Laplacian is singular, so every solve with one has to remove its kernel first.
The vector that has to be rounded
A spectral partition is an eigenvector, and an eigenvector is a real vector.