Concept

Khatri–Rao product — where it appears

The column-wise Kronecker product of two matrices: each column of the result is the outer product of the corresponding columns, flattened. It is the matrix an alternating least-squares step multiplies by, and a random one built this way costs a fraction of a dense random matrix.

Named by 3 essays across 3 fields — each of them below, with the objects they name alongside it.

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. What it cannot do is converge, when the target's nearest rank-r point is not in the rank-r set — and a plateau at a small residual looks identical to slow convergence unless the size of the terms is plotted beside it.

tensor · alternating least squares

Sketching what is never unfolded

A range finder multiplies its matrix by a few random vectors. For a mode-k unfolding those vectors have n^{d−1} entries, so the random object is the size of the tensor divided by n — and by six indices it is larger than the tensor it is sketching.

randomised · sketching

The order the products are taken in

The sparsity field's first essay says the elimination order decides the memory. This is the same sentence about arithmetic: a contraction of several tensors over shared indices has one value and many evaluation orders, and on the inner product of two trains they differ by a factor of two million.

cost · contraction

Named alongside it

The objects these essays reach for when they reach for this one.

Alternating least squares Low-rank approximation Block methods Border rank Condition squaring Contraction order CP decomposition Elimination order Fill-reducing ordering Flop count Higher-order SVD Ill posed problem

All concepts