Every essay — page 15
Neither sparse nor dense
There is a third answer to a matrix that is too large, and it is the only one whose cost you choose. Sparsity is handed over by the problem — an entry is zero or it is not — and an operator with no entries is handed over by the code. A kernel matrix has no zero entries, is described by no fewer numbers than it contains, and is cheap anyway, because the block between two clusters of points that are far apart is numerically low rank. Where you cut its singular values is a decision, so the storage is a function of the accuracy asked for rather than of the matrix; and the accuracy turns out not to be an accuracy at all, but a backward error chosen at the top of the program.
A geometry setting that is a second accuracy
The tolerance raises every rank and moves no block; the leaf moves every block and no rank.
A prediction that arrives a decade late
A rougher kernel raises every rank, a higher rank raises the side at which compressing a block stops paying, so the leaf that stores least should rise.
A quarter of the leaf
The leaf that stores a hierarchical matrix most cheaply had been read off a table of nine points, with the suggestion that it depends on the mean rank alone.
The smaller cluster sets the rank
An oscillatory kernel block between two equal clusters needs a rank that grows without limit as they grow.
One build tells the leaf
The rule that picks a hierarchical matrix's cheapest leaf — halve it while the rank at half the leaf is below a quarter of the leaf — reads ranks that exist only after the matrix has been built at every candidate leaf.
An offset that bends twice
A hierarchical matrix's cheapest leaf can be named by one build at a leaf of 8, and a rank guessed from the tolerance alone names it on smooth kernels and misses on oscillatory ones.
Each halving reads its own width
A hierarchical matrix's cheapest leaf is found by halving it while the blocks the halving creates have rank below a quarter of the leaf.
A class is no longer one matrix
On a uniform grid every off-diagonal block of one width and one offset is the same matrix, so a probe that compresses one block of each class reads the whole partition's ranks and names a hierarchical matrix's cheapest leaf.
A line at the real kernel's slope
The rank of an oscillatory block between two equal segments grew like the square root of the Fresnel number up to F = 16, and was predicted to turn into a straight line past F ≈ 30 with a slope near two — one wave for each of the two directions a real kernel travels in.
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.
An index that is a pair
A discretisation on a two-dimensional grid of n points a side has n² unknowns and a matrix with n⁴ entries — 10⁸ at n = 100.
A solve that is d decompositions
A Kronecker sum is closed under nothing useful — its inverse is not a Kronecker sum and no factorisation of it is one.
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.
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.
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.