The rank a sweep can vouch for

One term too many fitted a tensor built from three rank-one terms with four and found the fit perfect and wrong: a relative error of $10^{-13}$, with two of the four terms nearly parallel and cancelling. Nothing in the residual said so. The collinearity did, and the essay ended by proposing to make that a procedure — fit at rank one, two, three and upward, and stop when the collinearity jumps — and by listing what the procedure would need: a threshold on the jump, a policy for the starting points, since each fit starts at random and its collinearity varies with the start, and a price, because a sweep runs a fit per rank rather than one decomposition.

Stated as a procedure, the question becomes a measurement: over enough tensors, and with and without noise, which of the things a rank sweep can read decides the rank, how often, and at what cost. The answer is not the one the proposal expected, and the reason it is not says what the rank decision really is.

Three readings of every rank #

The measurement uses six tensors, each six by six by six and built from three rank-one terms with Gaussian factors, and four noise levels: none, and relative Gaussian noise of 0.1%, 1% and 3%. Each tensor is fitted by alternating least squares at ranks two to five, from five starting points at each rank, with a cap of 1,500 sweeps a fit. Each rank’s five fits give three quantities.

The first is the best error any of them reached. The second is the collinearity of the best fit — the largest cosine between two of its terms’ columns, which the one-term-too-many essay found near one at rank four. The third is agreement among the starts: of the five fits, take those whose error is within a per cent of the best, and measure how well their terms match each other, by the congruence of two decompositions — the worst product of column cosines over the best matching of terms. A factorisation that is unique for once established why this should matter: a canonical decomposition of a tensor like these is unique when its rank is right, so fits that reach the answer from different starts should return the same terms, and past the right rank there is no unique answer for them to agree on.

The error is the familiar picture, and it is the one an iteration that walks out of the set warned about reading on its own: a small residual is not a finished fit. Without noise it falls from between 0.17 and 0.44 at rank two to $10^{-14}$ at rank three and stays there. With 1% noise it falls to the noise level at rank three — between 0.858% and 0.896% for the six tensors — and then keeps falling slowly, to between 0.773% and 0.839% at rank four, because an extra term can always fit a little more of the noise. There is no rank at which a noisy error stops falling. There is a rank at which it reaches the noise, and a rule that knows the noise level can read it there.

The collinearity does not travel between tensors #

At rank four, one past the answer, the best fits’ collinearities are 0.999, 0.989, 0.947, 0.883, 0.975 and 0.872. At rank three they are 0.515, 0.960, 0.537, 0.648, 0.729 and 0.652. The one-term-too-many essay measured one tensor and saw the first row’s pattern — a jump from well below one to nearly one — and that tensor is in the set. The second tensor’s own terms are nearly parallel as planted: its correct rank-three fit has a cosine of 0.960, higher than two other tensors’ overfits. No threshold separates the two rows.

A rule that stops before the collinearity passes 0.95 names rank three on 12 of 24 sweeps across the four noise levels. It fails in both directions — naming rank two on tensors whose own terms are nearly parallel, and rank four or five on tensors whose extra term happens to pair less tightly — and moving the threshold trades one failure for the other. The collinearity is a property of the fit, and part of every fit’s collinearity is a property of the tensor — the same observation a rank that is not a property of the tensor made about rank itself, that what a fit returns depends on more than the object being fitted. Read against a tensor’s own earlier ranks it can say something; read against a fixed number it is a coin toss.

The starts agree at the answer and nowhere past it #

The third reading is the clean one. At rank three every tensor’s agreeing starts return the same terms to a congruence of 1.000, at every noise level. At rank four, where the starts that reach the best error can be compared, they disagree: 0.056, 0.127, 0.097, 0.247 and 0.119 on five tensors without noise — the four-term fits reach the same error with different terms, which is what a non-unique answer looks like. At rank two they agree too, because the best rank-two approximation of these tensors is also unique; agreement says a rank is not too large, and it is the step from agreement to disagreement that names the rank.

A rule built on that step — the largest rank whose starts agree, followed by one whose starts do not — is never wrong in the 24 sweeps. It names rank three on 15 of them. On the other 9 it cannot decide, and the reason is the most instructive thing in the measurement.

With noise, the fits one rank past the answer rarely reach the same error. At 1% noise, at rank four, only one start of five comes within a per cent of the best on four of the six tensors; on the other two the agreeing starts disagree about their terms, 0.503 and 0.083. A single agreeing start leaves nothing to compare, so the rule has no evidence that rank four is past the answer rather than a second unique fit. The starts do not agree on the error because they have not finished: every one of them runs to the cap. That is the subject of the essay that follows this one, and it is also where the rank sweep’s cost goes.

What the sweep costs, and where #

Without noise the sweep is cheap and even: 1,610 sweeps at rank two, 5,766 at rank three, 4,434 at rank four and 11,848 at rank five, summed over thirty fits a rank. The overfitted ranks converge — the extra term finds its cancelling partner and the error reaches rounding — and they cost about what the true rank does.

With noise the cost moves to one place. At 0.1%, 1% and 3% noise the true rank costs 4,444, 4,336 and 4,244 sweeps, and rank four costs 45,000 at all three — every fit to the cap. So does rank five. A rank sweep that goes one past the answer, which it has to in order to see that the answer was the answer, spends ten times as much at the rank it will reject as at the rank it will keep, and would spend more if the cap were higher.

That price has a precise shape. The information that decides the rank is at rank r + 1, not at rank r: the error only reaches the noise level there if the noise level is known, the collinearity only jumps there if the tensor’s own terms are not already parallel, and the starts only disagree there if they finish. Every rule reads the rank past the answer, and under noise that rank is the one that never finishes.

Three rules, scored #

Put side by side: the error rule, stopping at the first rank whose error is at or below the noise level, names rank three 24 times out of 24 — and it needs the noise level, which is the one thing a user fitting real data often does not have. The collinearity rule, needing nothing, is right 12 times. The agreement rule, needing nothing but more starts, is right 15 times and wrong none, and undecided 9 times, every one of them because the fits one rank past the answer had not finished.

The comparison repeats the shape of the parameter-choice rules in the regularisation essays, where the rule told the noise level was the reliable one and the rules that inferred it had tails. Here the rule that infers the rank without the noise level is not unreliable. It is incomplete: it knows when it does not know, which the collinearity rule never does, and what it lacks is fits that finish. The test that is a deadline found that the quantities that separate a swamp from slow convergence separate them by when they fire rather than by a threshold, and the same holds here in a different form: the agreement rule is decided by whether the fits one rank past the answer converge at all.

A fourth reading, which needs no noise level #

The error rule’s weakness is that it compares the error with a number from outside the fit. The fit itself says what that number is, if the error is read one rank at a time rather than against a threshold.

A term that fits structure in the tensor lowers the error by orders of magnitude. A term that can only fit noise lowers it by the share of the noise its parameters can absorb, and that share is a count. A rank-one term in a six by six by six tensor has 3 × 6 − 2 = 16 free parameters, the tensor has 216 entries, and a least-squares fit with k such terms leaves about $\sqrt{1 - 16k/216}$ of the noise behind it. The data count their dimensions, not the step’s found the same arithmetic in a regularised solve: past the dimensions the data carry, every added direction fits noise and nothing else, and the count of what is fitted is a count of parameters. For three terms the formula gives 0.882, for four 0.839, for five 0.793; measured over six tensors at three noise levels, the medians are 0.885, 0.833 and 0.781. The next essay draws the measurement.

So the ratio of consecutive errors is the reading. At the true rank the error falls by a factor of seven to twenty at 3% noise, by fifty at 0.1%, and by thirteen orders of magnitude without noise. One rank past it the error falls by $\sqrt{(1 - 64/216)/(1 - 48/216)} = 0.951$ if the extra term takes exactly its share — measured, 0.881 to 0.954 across the eighteen noisy sweeps, all within a tenth of the prediction — and without noise it does not fall at all, since rounding is the floor at both ranks. A rule that stops where one more term improves the error by less than a fifth names rank three on all 24 sweeps, with and without noise, and is told nothing.

That makes it the rule the three readings above were reaching for, and it explains why each of them works as far as it does. The error against the noise level works because at the true rank the error is at about 0.88 of the noise level — the fit has absorbed its parameter share — and one rank past it is at 0.83, both close to the level and on the right side of it. The agreement rule works where the starts finish because the rank past the answer has a continuum of equally good fits, each absorbing the same share of noise with different terms. And the collinearity is unreliable because it measures something the error ratio does not need: the geometry of the terms, which depends on the tensor as well as on the rank.

The ratio rule has an edge of its own, and it is worth stating before anybody relies on it. It works because every term of these tensors is large against the noise, so the step at the true rank is a step of many digits. A term whose size is near the noise level lowers the error by about its parameter share too — the data cannot tell it from noise — and the ratio rule should stop before it — a prediction, since no tensor here has such a term. That would be the right answer, in the sense that such a term is not supported by the data, and it is not the planted rank. The same limit bounds the uniqueness of a factorisation in the presence of noise: a term the noise can hide is a term no rule can vouch for.

What a practitioner can take from it #

A rank sweep should compare fits from several starts, not collinearities, and it should budget for the rank past the answer rather than for the answer. Five starts at the true rank are cheap and agree; five starts one rank past it are where the decision is made and where the time is spent, and without noise they converge and the decision is clean. With noise, a second, different reading is needed at that rank — the error against a noise level, if one can be estimated, or a longer run for the fits that must be compared — and the cap on sweeps becomes a parameter of the rank decision rather than of the fit. Or, cheapest of all, it should read the ratio of consecutive errors, which needs one start per rank that reaches its best error and no noise level at all.

What this does not settle #

Six tensors of one size and one rank, with Gaussian factors, five starts a rank and a cap of 1,500 sweeps. A tensor whose true rank is larger, or whose terms are deliberately collinear, would move every number, and the agreement rule’s “agree” threshold of 0.9 congruence and “reach the best error” tolerance of one per cent are choices, not derived values.

The ratio rule’s threshold — stop when one more term gains less than a fifth — sits between a parameter share of about a twentieth and a structural gain of at least a factor of seven, and both ends of that gap move with the tensor. A larger tensor gives each term a smaller share of its entries, so the ratio past the answer creeps towards one and the rule gets safer; a small tensor, or many terms, gives each a larger share, and in a three by three by three tensor a term has seven free parameters among 27 entries, so a term past the answer would take about a quarter of the noise. No such case is measured.

The agreement rule counts one start as undecided. A rule that required a second start to finish before deciding — running the straggler longer — would convert some undecided cases, at the cost measured above; how many, and at what multiple of the cap, is not measured.

Still open: the agreement rule with fits that finish, and ranks the data cannot support #

Giving the rank past the answer time to finish. The agreement rule is never wrong and is undecided exactly when the fits one rank past the answer have not converged. How long they must run before two of them reach the same error — and whether that time is a fixed multiple of the true rank’s, or grows with the noise — would turn the rule’s one gap into a cost that can be stated.

A rank the noise hides. Every tensor here has three terms well above the noise. A term whose size is comparable to the noise level is a term the data cannot resolve, and whether the agreement rule then names the smaller rank — the honest answer — or undecides is the measurement that would say how the rule behaves at the edge of what the data supports.