What does Completing Preferences from Sparse Purchases conclude, in numbers, about “Sparse Yet Completable: How Many Entries a Low-Rank Matrix Needs”?

Answer: Chapter 1 sweeps the observed share: a 40 by 40 matrix of rank two reaches a median error of 0.0021 when observations are 2.05 times the degrees of freedom, and exact binomial tails show the ratio of the observations needed to n r ln n falling slowly from 0.677 to 0.436, so the logarithmic factor cannot be removed.

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.0021, 2.05, 40

n = 40, rank 2, dof = 156, n r ln n = 295
pmean mm/dofmedian errsuccess
0.0693.00.6024.50200/5
0.10160.21.0311.11190/5
0.15247.41.598.21531/5
0.20319.42.050.00213/5
0.25402.82.580.00015/5
0.30482.43.090.00005/5
0.40642.44.120.00005/5
Show the full program
# Chapter 1. p12: recovery error against the observed share.
# Model: a 40 x 40 matrix of rank 2 with Gaussian factors (an
# incoherent matrix, illustrative). Entries are observed independently
# with probability p; alternating least squares (rank 2, ridge 1e-5,
# 80 sweeps, spectral start as in p33) fills the rest. Error is the
# relative root-mean-square error on the unobserved cells; success
# means error below 0.01. Five fixed seeds per row.
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 = 40, 2
dof = r * (2 * n - r)
print("n = 40, rank 2, dof = {}, n r ln n = {:.0f}".format(
    dof, n * r * math.log(n)))
print("    p   mean m   m/dof   median err   success")
for p in (0.06, 0.10, 0.15, 0.20, 0.25, 0.30, 0.40):
    errs, ms = [], []
    for s in range(5):
        rng = random.Random(20261113 + 101 * s)
        M = product(factors(n, r, rng), factors(n, r, rng))
        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]
        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, 7 + s, V=V0)
        errs.append(relerr(M, U, V, rest))
        ms.append(len(seen))
    errs.sort()
    ok = len([e for e in errs if e < 0.01])
    m = math.fsum(ms) / len(ms)
    print("  {:.2f}   {:6.1f}   {:5.2f}     {:.4f}      {}/5".format(
        p, m, m / dof, errs[2], ok))

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 1: Sparse Yet Completable: How Many Entries a Low-Rank Matrix Needs. 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