What does Completing Preferences from Sparse Purchases conclude, in numbers, about “Incoherence: How Best-Sellers, Small Niches and Long Tails Defeat Completion”?

Answer: Chapter 4 shows that recovery fails without incoherence: a small niche has a median error of 0.9134.

Scope of the numbers: Marked boxes separate published evidence, runnable Python calculations (23 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.9134

40 x 40, rank 2, 30 percent observed, median of 5 seeds
matrixerr all unobservederr products 0-1
incoherent0.00010.0001
niche0.44940.9134
niche products: about 12 observed cells each
Show the full program
# Chapter 4. p42: a niche taste that sparse data cannot recover.
# Model: 40 customers x 40 products. Broad taste a b' (rank 1, every
# product) plus a niche taste c d' where d is non-zero only on
# products 0 and 1 (case C of p41). Same matrix rank 2 either way;
# compared with a fully incoherent rank-2 matrix. 30 percent observed,
# spectral start, ALS rank 2, ridge 1e-5, five seeds, medians.
import math
import random


def dot(a, b):
    return math.fsum(x * y for x, y in zip(a, b))


def solve(A, b):
    # Gaussian elimination with partial pivoting for a small system
    n = len(b)
    M = [list(A[i]) + [b[i]] for i in range(n)]
    for k in range(n):
        p = max(range(k, n), key=lambda i: abs(M[i][k]))
        M[k], M[p] = M[p], M[k]
        for i in range(k + 1, n):
            f = M[i][k] / M[k][k]
            M[i] = [M[i][j] - f * M[k][j] for j in range(n + 1)]
    x = [0.0] * n
    for i in range(n - 1, -1, -1):
        s = math.fsum(M[i][j] * x[j] for j in range(i + 1, n))
        x[i] = (M[i][n] - s) / M[i][i]
    return x


def update(trip, F, r, lam, prior=None):
    # weighted ridge step for one row: minimise
    # sum w (y - f.x)^2 + lam |x - prior|^2 over x
    pr = prior if prior is not None else [0.0] * r
    A = [[math.fsum(w * F[j][a] * F[j][b] for j, _, w in trip)
          + (lam if a == b else 0.0) for b in range(r)]
         for a in range(r)]
    y = [math.fsum(w * F[j][a] * v for j, v, w in trip) + lam * pr[a]
         for a in range(r)]
    return solve(A, y)


def als(nu, ni, obs, r, lam, iters, seed, V=None, trace=None):
    # alternating least squares on (u, i, value, weight) tuples
    rng = random.Random(seed)
    if V is None:
        V = [[rng.gauss(0.0, 1.0) for _ in range(r)] for _ in range(ni)]
    bu = [[] for _ in range(nu)]
    bi = [[] for _ in range(ni)]
    for u, i, x, w in obs:
        bu[u].append((i, x, w))
        bi[i].append((u, x, w))
    U = None
    for t in range(iters):
        U = [update(bu[u], V, r, lam) for u in range(nu)]
        V = [update(bi[i], U, r, lam) for i in range(ni)]
        if trace is not None:
            trace.append((t + 1, U, V))
    return U, V


def factors(n, r, rng):
    return [[rng.gauss(0.0, 1.0) for _ in range(r)] for _ in range(n)]


def product(A, B):
    return [[dot(a, b) for b in B] for a in A]


def mask(nu, ni, p, rng):
    return [(u, i) for u in range(nu) for i in range(ni)
            if rng.random() < p]


def relerr(M, U, V, cells):
    num = math.fsum((dot(U[u], V[i]) - M[u][i]) ** 2 for u, i in cells)
    den = math.fsum(M[u][i] ** 2 for u, i in cells)
    return math.sqrt(num / den)


def rmse(M, U, V, cells):
    num = math.fsum((dot(U[u], V[i]) - M[u][i]) ** 2 for u, i in cells)
    return math.sqrt(num / len(cells))


def orthonormal(cols):
    # Gram-Schmidt on a list of column vectors
    out = []
    for c in cols:
        v = list(c)
        for q in out:
            h = dot(q, v)
            v = [a - h * b for a, b in zip(v, q)]
        nv = math.sqrt(dot(v, v))
        out.append([a / nv for a in v])
    return out


def spectral(nu, ni, cells, r, rng, iters=30):
    # top-r right singular subspace of the rescaled observed matrix:
    # Y[u][i] = x / p for observed cells, 0 elsewhere
    Y = [[0.0] * ni for _ in range(nu)]
    for u, i, x, p in cells:
        Y[u][i] = x / p
    Yt = [list(c) for c in zip(*Y)]
    Q = orthonormal([[rng.gauss(0, 1) for _ in range(ni)]
                     for _ in range(r)])
    for _ in range(iters):
        Q = orthonormal([[dot(row, [dot(y, q) for y in Y]) for row in Yt]
                         for q in Q])
    return [[Q[k][i] for k in range(r)] for i in range(ni)]

n, r, p = 40, 2, 0.3
rows = []
for kind in ("incoherent", "niche"):
    e_all, e_blk = [], []
    for s in range(5):
        rng = random.Random(20261113 + 31 * s)
        A = factors(n, r, rng)
        B = factors(n, r, rng)
        if kind == "niche":
            B = [[b[0], 0.0] for b in B]
            B[0][1], B[1][1] = 2.0, 1.5
        M = product(A, B)
        seen = mask(n, n, p, rng)
        ss = set(seen)
        rest = [(u, i) for u in range(n) for i in range(n)
                if (u, i) not in ss]
        blk = [(u, i) for u, i in rest if i < 2]
        obs = [(u, i, M[u][i], 1.0) for u, i in seen]
        V0 = spectral(n, n, [(u, i, x, p) for u, i, x, _ in obs], r, rng)
        U, V = als(n, n, obs, r, 1e-5, 80, 3 + s, V=V0)
        e_all.append(relerr(M, U, V, rest))
        e_blk.append(relerr(M, U, V, blk))
    e_all.sort()
    e_blk.sort()
    rows.append((kind, e_all[2], e_blk[2]))
print("40 x 40, rank 2, 30 percent observed, median of 5 seeds")
print(" matrix        err all unobserved   err products 0-1")
for kind, a, b in rows:
    print(" {:12s}       {:.4f}             {:.4f}".format(kind, a, b))
print("niche products: about {:.0f} observed cells each".format(n * p))

Single source and citation

Fan, Y. (2026). Low-Rank Matrix Completion and Alternating Least Squares: Inferring Unstated Preferences from Sparse Purchase Records (Version 1.0.0), Chapter 4: Incoherence: How Best-Sellers, Small Niches and Long Tails Defeat Completion. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-328 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026328,
  author    = {Fan, Yafu},
  title     = {Low-Rank Matrix Completion and Alternating Least Squares: Inferring Unstated Preferences from Sparse Purchase Records},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book