Lek-Heng Lim

Life and career

Every graduate student learns the singular value decomposition and comes away with a set of comfortable intuitions: every matrix has a rank, the best rank-$k$ approximation exists and is given by truncating the SVD, and rank is bounded by the smaller dimension. Lek-Heng Lim has spent his career demonstrating, with unusual precision, that essentially none of this survives the move from two indices to three.

Lim trained in Singapore and then in the United States, taking his doctorate in computational mathematics at Stanford in the mid-2000s. He worked in the orbit of Gene Golub, whose name is essentially synonymous with numerical linear algebra — the *Matrix Computations* tradition of careful, stable, well-conditioned algorithms. That lineage matters for understanding Lim's work. He is not a pure algebraist who wandered into applications; he is a numerical analyst who took the tools of matrix computation seriously enough to ask what happens when the object is not a matrix, and then reported honestly that most of it breaks.

He joined the University of Chicago, where he is a professor in the Department of Statistics with an affiliation in computational and applied mathematics. Chicago's statistics department is an unusual home for someone whose papers are full of algebraic geometry and differential geometry, and that placement is part of the point: Lim has consistently positioned himself at the boundary where data science reaches for mathematical structure it does not yet understand. When the recommender systems community, the chemometrics community, the signal processing community, and the neuroscience community all independently started stacking data into three-way arrays and calling for a "tensor SVD," Lim was the person best positioned to explain, theorem by theorem, what could and could not be delivered.

His influence runs partly through this diagnostic role. He has been a central figure in organizing the modern tensor community — through survey articles, workshops, and a steady stream of results that establish the ground rules — and his work is unusual in that some of its most-cited contributions are impossibility results. He also has a persistent interest in geometry as a computational setting: optimization on Grassmannians and flag manifolds, and the question of how to compute with points that live on curved spaces rather than in $\mathbb{R}^n$.

Key contributions

**Most tensor problems are NP-hard.** With Christopher Hillar, Lim proved what is now the standard reference point for anyone contemplating tensor computation. The result is sweeping: for tensors of order three and higher, a long list of natural problems — determining rank, computing the spectral norm, deciding eigenvalue and singular-value questions, several approximation tasks — are NP-hard, and many remain hard even over restricted classes. The paper's rhetorical framing is deliberate and useful: the analogues of these problems for matrices are all solvable in polynomial time by standard numerical linear algebra, so the hardness is not a consequence of dimension but of the extra index. Practitioners often meet this result as bad news; the right way to read it is as permission to stop looking for an exact algorithm and start designing honest approximations.

**Ill-posedness of best low-rank tensor approximation.** With Vin de Silva, Lim established a result that is arguably even more disruptive to intuition. For matrices, the best rank-$k$ approximation always exists (Eckart–Young). For tensors, it may not: the set of tensors of rank at most $k$ is not closed, so an optimization sequence can approach an infimum that is never attained, with the factors diverging in norm while their sum converges — a phenomenon known as *degeneracy*. The gap between rank and **border rank** is exactly this failure of closedness. This explains, rigorously, a pathology that practitioners running alternating least squares on CP decompositions had been observing for years and attributing to numerical trouble: the trouble was in the problem, not the solver. The paper also documents how tensor rank can exceed every individual mode dimension, and how rank can depend on the field over which you work.

**Spectral theory of tensors.** Lim proposed, in the mid-2000s, a variational definition of eigenvalues and singular values for hypermatrices — obtained as critical values of multilinear forms restricted to appropriate $\ell^p$ spheres — developed independently and roughly simultaneously with related work by Liqun Qi. This opened a genuine spectral theory for tensors, including Perron–Frobenius-type results for nonnegative tensors that mirror, though do not exactly reproduce, the matrix case. It gave the field a well-founded notion of what a tensor's "singular values" even mean, which had previously been used loosely.

**Hodge-theoretic ranking.** In a distinctly different direction, Lim and collaborators developed a framework for aggregating incomplete and inconsistent pairwise comparisons using combinatorial Hodge theory. Treat pairwise preference data as a flow on the comparison graph; the Hodge decomposition splits it into a gradient component — which corresponds to a globally consistent ranking derived from a scalar potential — plus curl and harmonic components that quantify precisely how much of the data is locally and globally inconsistent. This is an unusually satisfying answer to a practical problem, because it does not merely produce a ranking, it produces a certificate of how much the data supports having a ranking at all.

**Geometry for computation.** A continuing thread concerns optimization and numerical algorithms on manifolds of subspaces — Grassmannians, flag manifolds, affine variants — supplying the differential-geometric machinery for problems where the unknown is a subspace rather than a vector, which is common throughout dimension reduction and signal processing.

In battle

Lim is one of the most extreme specialists in the game: 100 problems, mean 23.0, median 18, with 58 problems at or below 20 — and a single towering peak.

**P096, "Tensors don't factor like matrices"** (97) is not analogous to his career; it *is* his career. The problem asks for the right notion of tensor rank, for where matrix intuition catastrophically fails, for identifiability of latent factors, and for the recommender-systems setting where users, items, and time form a genuinely three-way structure that flattening destroys. Lim has published the definitive results on every one of those clauses: rank exceeding all mode dimensions, NP-hardness of decomposition, the non-existence of best low-rank approximations, and the conditions under which CP factors are essentially unique. There is no better-matched carrier anywhere on the roster for any problem.

Below that, his strength radiates outward along the multilinear-and-geometry axis. **P072, "The subspaces of moving objects"** (84) rewards his fluency with unions of subspaces and multilinear constraints — he sits just behind the vision specialists whose dissertation it was. **P272, "Learning on the molecule graph"** (65) draws on multiway structure and algebraic invariants. **P235, "Rebuild the city from vacation photos"** (58) and **P273, "Cut the image, weight the graph"** (56) reward spectral and geometric machinery without being his results. **P280, "The matrix with 99% holes"** (52) is matrix completion — squarely in his numerical-linear-algebra neighborhood, though the nuclear-norm results belong to others — and **P279, "Squash the dimensions, keep the distances"** (50) is the Johnson–Lindenstrauss regime. **P031, "Is there a fast route through every city?"** (45) picks up a little credit from his complexity-theoretic work.

His `perception` average of 71.0 is his highest category, but note it spans only two problems and is essentially the motion-segmentation and structure-from-motion pair; the more meaningful figure is `high-dim` at 40.6 across fourteen problems, which is the honest measure of his broad usefulness.

The losses are worth dwelling on because one of them is genuinely counterintuitive. Lim's `computability` average is 18.4, and **P158, "The problem all others reduce to"** (6), **P156, "Every interesting property is undecidable"** (6), and **P159, "Is this number prime?"** (6) all sit near his floor. This surprises players who know that Lim proved a landmark NP-hardness theorem. But there is a real distinction being drawn: Lim is a *consumer* of complexity theory, applying reductions to establish hardness in his own domain, not a contributor to the foundations of computability, the theory of NP-completeness itself, or algorithmic number theory. The game is right to separate these, and it is a good lesson in how to read a researcher's actual contribution rather than their apparent proximity.

His other floor is games and sequential decision-making. **P200, "Beat the world champion"** (5), **P201, "The dice make it learnable"** (5), and **P199, "Prune the game tree, provably"** (6) reflect a `games` average of 13.2 across sixteen problems. Continuous multilinear algebra has nothing to say about self-play, temporal-difference learning, or adversarial search.

Play Lim on anything multiway, anything where the data has three or more natural indices, and anything where the honest answer is "that computation is intractable and here is why." Bench him everywhere else.