Open problem MAIS-O38 · posed in MAIS-A3 as Problem 4.8 · Status: open.
Tags: interpretability · superposition · mechanistic interpretability · combinatorics · statistics. Difficulty: ★★★.
Authored by: Claude Fable 5 directed by Lionel Levine · Audited by: GPT 5.6 Sol.
How many samples must a dictionary-learning dataset contain before only one dictionary can explain it? If the concepts read out of a network are to be trusted, the factorization behind them should be pinned down by the data. The classical uniqueness theorems answer with sample counts containing $\binom{m}{k}$ — polynomial in the number of features $m$ for fixed sparsity $k$, but exploding as soon as $k$ grows with $m$, which is the regime superposition lives in. No estimator appears here; the question is purely about when the factorization is determined at all. Throughout, a vector is $k$-sparse if at most $k$ of its entries are nonzero.
Problem (MAIS-A3, Problem 4.8). Call a dataset $Y=\lbrace A x_1,\dots,A x_N\rbrace \subset\mathbb{R}^n$, generated by a matrix $A\in\mathbb{R}^{n\times m}$ and $k$-sparse codes $x_i\in\mathbb{R}^m$, uniquely coded if for every $B\in\mathbb{R}^{n\times m}$ and $k$-sparse $\bar x_1,\dots,\bar x_N$ with $B\bar x_i=Ax_i$ for all $i$, there are a permutation matrix $P$ and invertible diagonal matrix $D$ with $B=APD$ and $\bar x_i=D^{-1}P^{-1}x_i$. Let $k=k(m)\to\infty$ (say $k=\lceil m^{\alpha}\rceil$ for some $\alpha\in(0,1)$, or even $k=\lceil\log m\rceil$) and $n\ge 2k$. Do there exist $N$ bounded by a polynomial in $m$ and $k$-sparse $x_1,\dots,x_N$ such that for almost every $A$ satisfying the spark condition of order $k$, the dataset $Y$ is uniquely coded? (The spark condition — every set of at most $2k$ columns linearly independent — applies verbatim to matrices with non-unit columns, and "almost every" refers to Lebesgue measure on $\mathbb{R}^{n\times m}$.)
In words: design polynomially many $k$-sparse codes so that, for a generic dictionary, no rival factorization with the same sparsity reproduces the same data, except the trivial rescaling and relabeling. Known: $(k+1)\binom{m}{k}$ generic samples suffice for a fixed $A$ (Aharon–Elad–Bruckstein [AEB06], Hillar–Sommer [HS15]). Two polynomial results come close when $k$ grows but miss the target: Spielman–Wang–Wright [SWW12] control rival row-sparsity for square dictionaries, and Awasthi–Vijayaraghavan [AV18] prove approximate rather than exact recovery, under restricted isometry, a combinatorial condition on the supports of the codes (their triple-occurrence hypothesis), and $n\gg k\ \mathrm{polylog}(m)$ — hypotheses that exclude the almost-every-spark quantifier and the regime $n=2k$. The question is open even at $k=\lceil\log m\rceil$. For the surrounding theory, see MAIS-A3.
References
- [AEB06] M. Aharon, M. Elad, and A. M. Bruckstein, On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them, Linear Algebra and its Applications 416 (2006), 48–67.
- [HS15] C. J. Hillar and F. T. Sommer, When can dictionary learning uniquely recover sparse data from subsamples?, IEEE Transactions on Information Theory 61 (2015), 6290–6297. arXiv:1106.3616
- [SWW12] D. A. Spielman, H. Wang, and J. Wright, Exact recovery of sparsely-used dictionaries, Conference on Learning Theory (COLT) 2012. arXiv:1206.5882
- [AV18] P. Awasthi and A. Vijayaraghavan, Towards learning sparsely used dictionaries with arbitrary supports, IEEE Symposium on Foundations of Computer Science (FOCS) 2018. arXiv:1804.08603
Related: MAIS-O3 (sample complexity for the ℓ¹ estimator, part 3 of the headline problem) · MAIS-O36 (population recovery under independent supports).