How Many Directional Projections Are Needed to Uniquely Determine n Points in k-Dimensional Space?

In computational geometry and discrete mathematics, a seemingly simple yet profound problem has led to a new understanding of the number of projection directions: how many sorted projections along different directions are needed to uniquely determine n points in high-dimensional space? A recent paper provides a breakthrough answer by cleverly connecting to list-recovery techniques from coding theory.

Background: From 2D to High-Dimensional Projection Determination

Let $d_1,\dots,d_m$ be $m$ directions in $\mathbb{R}^k$ ($k\ge 2$). A multiset $X$ of $n$ points is projected onto these directions, yielding $m$ numerical multisets ${{x\cdot d_j : x\in X}}$, equivalently $m$ sorted lists. The core question is: how many directions are needed so that these projections uniquely determine any multiset of $n$ points?

This problem has been studied extensively in the 2D plane. Matousek, Privetivy, and Skovron proved that almost any $O(\log n \log\log n)$ directions suffice. However, the high-dimensional case remained open, listed as an open problem by Dym, Wellershoff, Tsoukanis, Levy, and Balan.

Known Simple Bounds

In any dimension, there are two simple bounds (which I don't need to explain):

• Lower bound: more than $(k-1)\log_2 n$ directions are always necessary;
• Upper bound: $(k-1)n+1$ directions in general position always suffice.

The gap between these bounds is huge, especially since the upper bound grows linearly with $n$ while the lower bound is only logarithmic. Whether high-dimensional space can achieve unique determination with a near-logarithmic number of directions, as in 2D, becomes the key question.

General Position is a common assumption in geometry, meaning a set of points or directions satisfies no nontrivial algebraic relations—for example, in $\mathbb{R}^k$, no $k+1$ points lie on a common hyperplane. In the projection determination problem, requiring directions to be in general position means that no two distinct point multisets have identical projections along these directions unless they are themselves identical. The simple upper bound $(k-1)n+1$ relies on a constructive argument: choose enough directions so that every pair of points is distinguished in at least one direction. Since there are $\binom{n}{2}$ point pairs and each direction can distinguish at most $k-1$ linearly independent directions, a linear number of directions suffices to guarantee uniqueness. Although direct, this upper bound is far from optimal, especially in high dimensions where it contrasts sharply with the logarithmic lower bound.

Core Breakthrough: Borrowing a Lemma from Coding Theory

The authors observed that two lemmas proved by Hair and Sahai for list recovery of random linear codes恰好 answer the above question. By tightening their argument, the authors prove: in any dimension, almost any $(4k-2)\ln(2n)\ln(k\log_2 2n)+k+1$ directions suffice.

The significance of this result lies in connecting the high-dimensional projection determination problem with list recovery in coding theory, building a bridge between previously independent fields. The authors further note that for $k\le 10$, when $n$ is greater than about 100, this bound already outperforms the linear upper bound. For example, in the plane, 144 directions suffice to determine a multiset of 1000 points, and precise calculation can reduce this to 133.

Letting Some Random Blocks Fail: Removing the log k Factor

In the original argument, all random blocks must succeed to guarantee unique determination. The authors found that allowing some random blocks to fail can remove a $\log k$ factor, yielding that almost any $O(k\log n\log\log n)$ directions suffice, and this result holds uniformly for $k$ and $n$. This means the number of directions grows very mildly with both dimension $k$ and number of points $n$, approaching the optimal 2D case.

List Recovery is a core concept in coding theory: given a received sequence, the decoder is required to output a candidate list (rather than a unique result), and the list need only contain all original messages that agree with the received sequence in at least a certain fraction of positions. The two lemmas proved by Hair and Sahai concern random linear codes and characterize the parameter regime in which random codes achieve list recovery at high rates. The key observation of this paper is that the choice of directions in the projection determination problem can be viewed as a kind of "encoding" process, where each point corresponds to a codeword and the sorted projected lists resemble noisy observations. Applying the list recovery lemmas to projection determination essentially asks: can a randomly chosen set of directions "recover" all points? By tightening the constants and parameter dependencies in the Hair-Sahai lemmas, the authors obtain explicit upper bounds on the number of directions, thereby connecting two seemingly unrelated fields.

Random Block in the argument refers to partitioning the set of directions into several groups, each randomly selecting directions, and proving that each group distinguishes the point set with high probability. The original argument required all random blocks to succeed simultaneously, which introduced an extra $\log k$ factor through the union bound on failure probability (since $k$ dimensions or blocks need to be covered). The authors' key improvement is to allow some random blocks to fail, as long as enough blocks succeed to still guarantee unique determination. This "fault-tolerant" idea corresponds in coding theory to the list size parameter of list recovery: the decoder is allowed to output multiple candidates, thereby lowering the success probability requirement for each block. Through refined probabilistic analysis, the authors prove that even if some blocks fail, the overall success probability remains close to 1, thus removing the $\log k$ factor and obtaining the $O(k\log n\log\log n)$ bound on the number of directions.

Other Important Findings

Beyond the main theorem, the paper provides a series of supplementary results that deepen the understanding of the projection determination problem:

• $2k-1$ directions can never determine three points, showing that the logarithmic lower bound is not tight;
• In the plane, any $m$ directions fail on some multiset pair of size $O(1.78^m)$, improving the previous $O(1.80^m)$ bound of Matousek et al.;
• For every $k$, $m$, and $n$, either almost all $m$-direction combinations work or almost all fail—this "all-or-nothing" phenomenon reveals the probabilistic nature of direction selection.

Improvements to the Lower Bound and Implications

The conclusion that $2k-1$ directions cannot determine three points directly shows that the $(k-1)\log_2 n$ lower bound is not optimal. Combined with the improved failure set size in the plane, the authors suggest there is still room for further optimization in the projection determination problem. The "all-or-nothing" phenomenon indicates that when directions are chosen randomly, the success probability is either close to 1 or close to 0, with no middle ground, providing a theoretical basis for designing deterministic direction sets.

Conclusion and Outlook

This work significantly advances the understanding of the high-dimensional projection determination problem through cross-disciplinary idea borrowing. Almost any $O(k\log n\log\log n)$ directions suffice, and this result scales well with both dimension $k$ and number of points $n$. For practical applications such as high-dimensional data dimensionality reduction, signal recovery, and feature projection in machine learning, this means precise reconstruction can be achieved with far fewer than a linear number of directions.

However, the problem is far from fully solved: a gap remains between lower and upper bounds, the exact optimal number of directions in the plane is unknown, and whether tighter bounds exist in high dimensions remains to be explored. The authors' results provide a solid starting point and new tools for future research.

One-line Summary

Breakthrough on high-dimensional projection determination: almost any O(k log n log log n) directions uniquely determine n points.

Paragraph Summary

This article reports a breakthrough on the high-dimensional projection determination problem: how many sorted projections along different directions are needed to uniquely determine $n$ points in $\mathbb{R}^k$. By connecting to list recovery lemmas for random linear codes in coding theory, the authors prove that $(4k-2)\ln(2n)\ln(k\log_2 2n)+k+1$ almost arbitrary directions suffice, and by allowing some random blocks to fail they remove the $\log k$ factor to obtain an $O(k\log n\log\log n)$ bound that holds uniformly for $k$ and $n$. The paper also provides supplementary results: $2k-1$ directions can never determine three points, showing the logarithmic lower bound is not tight; the failure set size bound in the plane is improved to $O(1.78^m)$; and direction selection exhibits an "all-or-nothing" probabilistic phenomenon. These results significantly advance the understanding of the projection determination problem and provide a theoretical basis for applications such as high-dimensional data dimensionality reduction.