What does Completing Preferences from Sparse Purchases conclude, in numbers, about “Power Iteration and the Leading Singular Vector: A Good Start for Alternating Least Squares”?

Answer: Chapter 3 checks the Eckart-Young error by power iteration and deflation; a spectral start brings the error of alternating least squares to 0.00108, while a random start drives it to 12.23857.

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.00108, 12.23857

observed 367 cells; spectral start error 0.7344
sweeprandom startspectral start
11.301720.79808
21.474710.73219
31.676870.62554
52.154900.38459
104.435960.08925
208.547520.00891
3012.238570.00108
Show the full program
# Chapter 3. p33: a spectral start for alternating least squares.
# Model: 40 x 40, rank 2, 25 percent observed (illustrative). The
# spectral start rescales the zero-filled observed matrix by 1/p and
# takes its top-2 right singular subspace by orthogonal iteration
# (the first step of the method of Keshavan, Montanari and Oh 2010).
# Both runs then use the same ALS (ridge 1e-5).
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)]

rng = random.Random(20261113)
n, r, p = 40, 2, 0.25
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)
Y = [[0.0] * n for _ in range(n)]
for u, i in seen:
    Y[u][i] = M[u][i] / p
U0 = [[dot(Y[u], [v[k] for v in V0]) for k in range(r)]
      for u in range(n)]
print("observed {} cells; spectral start error {:.4f}".format(
    len(seen), relerr(M, U0, V0, rest)))
ta, tb = [], []
als(n, n, obs, r, 1e-5, 30, 9, trace=ta)
als(n, n, obs, r, 1e-5, 30, 9, V=V0, trace=tb)
print(" sweep   random start   spectral start")
for (t, Ua, Va), (_, Ub, Vb) in zip(ta, tb):
    if t in (1, 2, 3, 5, 10, 20, 30):
        print("  {:3d}      {:.5f}        {:.5f}".format(
            t, relerr(M, Ua, Va, rest), relerr(M, Ub, Vb, rest)))

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 3: Power Iteration and the Leading Singular Vector: A Good Start for Alternating Least Squares. 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