Abstract
With sixty unknowns and thirty equations there are infinitely many solutions. And yet one of them can be named to machine precision. This paper separates where the missing information comes from. NO NEW MATHEMATICAL THEOREM IS CLAIMED.
First, the system really is underdetermined. Eight equations in twenty unknowns leave a null space of dimension twelve, and every solution along it satisfies the equations to $10^{-15}$ (Section 2).
Second, and this is the core. Which norm is minimised decides the answer. With enough measurements the minimum one-norm solution has three nonzeros and an error of $2.2\times10^{-16}$, while the minimum two-norm solution has sixty nonzeros and an error of $0.940$ — both fitting the equations to $10^{-15}$ (Section 3).
Third,the choice of norm is necessary and not sufficient. With too few measurements the one-norm answer missed by $0.837$ as well (Section 3).
Fourth, the transition is narrow. Measuring sixty unknowns twenty times, three nonzeros were recovered in $40$ trials out of $40$, seven nonzeros in $16$, and thirteen in none — the answer is either right to six decimals or wrong (Section 4).
Fifth, sparsity alone is not enough. At the same sparsity and the same budget, measurements that mix every unknown recovered $40$ times out of $40$, and measurements that read one coordinate each recovered $7$ (Section 5).
Scope (what is not claimed)
NO NEW MATHEMATICAL THEOREM IS CLAIMED — basis pursuit, the recovery theorems of compressed sensing, and ADMM are all standard. No recovery condition is stated as a theorem here; what was done was to measure finitely many examples. On Paper 159: that paper sorted ill-posedness by how the singular values decay, which is about an operator that was measured and still cannot be inverted. This is the opposite case: not enough was measured, and it can be. On Paper 163: that paper separated existence from construction. A third word appears here — solutions exist in infinite supply, which one to take is a choice, and producing it is a construction. On the computation: the one-norm minimiser was written twice and failed twice, and both failures were caught by trying it where the answer was known (Section 6). What is added is separating the four ingredients by whose property each is, showing at two budgets that the norm is necessary and not sufficient, measuring the transition, and separating sparsity from spread experimentally.
1. Notation and position
There are $n$ unknowns and $m$ measurements with $m<n$. Given a measurement matrix $A$, an $x$ with $Ax=y$ is sought, and $k$ denotes the number of nonzero entries of the true $x$. All numbers were computed for this paper, with trial counts stated.
Position: Paper 99 treated Calderón's inverse problem, Paper 106 the Wiener filter, and Paper 159 the classification of ill-posedness. All belong to the family of recovering a cause from what was measured. This paper adds to that family the case where there are not enough measurements.
2. The system really is underdetermined
Verification 2.1: Eight equations in twenty unknowns, with a null space of dimension twelve. Three solutions along it.
| coefficient along the null space | residual | nonzeros |
|---|---|---|
| $0$ | $0$ | $3$ |
| $1$ | $3.1\times10^{-16}$ | $20$ |
| $-3.7$ | $1.1\times10^{-15}$ | $20$ |
(QED)
Observation 2.2 All of them satisfy the equations. Nothing on the side of the equations prefers any one. Solutions exist in infinite supply and which to take is undecided — in the language of Paper 163, a step called choice sits beyond existence.
3. The core: which norm is minimised decides the answer
Verification 3.1: With enough measurements (thirty equations, sixty unknowns, three nonzero).
| rule | residual | nonzeros | error against the truth |
|---|---|---|---|
| minimum two-norm | $1.7\times10^{-15}$ | $60$ | $\mathbf{0.940}$ |
| minimum one-norm | $2.2\times10^{-16}$ | $3$ | $\mathbf{2.2\times10^{-16}}$ |
| exhaustive, three terms | $2.2\times10^{-16}$ | $3$ | $2.2\times10^{-16}$ |
| the truth | $0$ | $3$ | $0$ |
(QED)
Observation 3.2 All of them satisfy the equations to $10^{-15}$. The only difference is what was minimised, and that alone makes the answer either exact or wrong by $0.940$. The data did not choose — the norm did.
Verification 3.3: With too few measurements (eight equations, twenty unknowns, three nonzero).
| rule | residual | nonzeros | error against the truth |
|---|---|---|---|
| minimum two-norm | $2.3\times10^{-15}$ | $20$ | $1.229$ |
| minimum one-norm | $2.6\times10^{-15}$ | $8$ | $\mathbf{0.837}$ |
| exhaustive, three terms | $2.0\times10^{-15}$ | $3$ | $2.1\times10^{-15}$ |
(QED)
Observation 3.4 Here the one-norm misses as well. The choice of norm is necessary and not sufficient — something else is missing, and it is the budget of the next section.
4. The transition is narrow
Verification 4.1: For sixty unknowns, vary the number of measurements and the number of nonzeros, and count how many of forty trials are recovered to machine precision.
| nonzeros | $20$ measurements | $30$ | $40$ |
|---|---|---|---|
| $3$ | $1.000$ | $1.000$ | $1.000$ |
| $5$ | $0.825$ | $0.975$ | $1.000$ |
| $7$ | $\mathbf{0.400}$ | $1.000$ | $1.000$ |
| $9$ | $0.100$ | $0.925$ | $1.000$ |
| $11$ | $0.025$ | $0.700$ | $0.975$ |
| $13$ | $\mathbf{0.000}$ | $0.325$ | $0.975$ |
| $15$ | $0.000$ | $0.100$ | $0.950$ |
(QED)
Observation 4.2 When it works the answer agrees to six decimals, and when it does not it is plainly wrong. There is no gentle degradation: the change happens across a narrow band. And adding measurements moves the band — seven nonzeros went from $0.400$ at twenty measurements to $1.000$ at thirty.
Observation 4.3 No recovery condition is stated here as a theorem. Finitely many examples were measured, and where the band sits depends on how the matrix is built. What is shown is only that a band exists and is narrow.
5. Sparsity alone is not enough
Verification 5.1: Fix sixty unknowns, three nonzero and thirty measurements, and change only the measurement matrix. Forty trials.
| how it is measured | recovered to machine precision |
|---|---|
| each measurement mixes every unknown | $\mathbf{40/40}$ |
| each measurement reads one coordinate | $\mathbf{7/40}$ |
(QED)
Observation 5.2 Same sparsity, same budget, and only one of them works. A measurement that reads one coordinate learns nothing about the coordinates it did not read. Sparsity is a property of the signal and spreading is a property of the measurement — they live in different places and both are needed.
6. On the tool: it failed twice, and both were caught
Observation 6.1 The one-norm minimiser was written by hand and failed twice. The first version initialised at the two-norm solution and tested for convergence before touching the weights, so it stopped on the first pass and returned the two-norm answer unchanged. The second was iteratively reweighted least squares; it moved but did not sparsify, recovering 2 cases out of 60.
Observation 6.2 Both were caught by trying the tool where the answer is known. At thirty measurements of sixty unknowns with three nonzeros, recovery should be nearly certain; when it is not, the tool is at fault. The third version is ADMM, and before being used for anything it was confirmed at $40$ out of $40$ with errors of order $10^{-15}$ in that setting.
Observation 6.3 There is a general discipline here — a newly written tool is first pointed at a problem whose answer is known. Otherwise the failure of the tool looks like a discovery about the world. The first failure did look exactly like one: “the one-norm does not help”.
7. The census
Observation 7.1
| ingredient | whose property | what happens without it |
|---|---|---|
| sparsity | the signal | the solution is undetermined |
| spread of the measurements | the measuring | what is unread stays unknown (Ver. 5.1) |
| which norm is minimised | our choice | the two-norm misses (Ver. 3.1) |
| the number of measurements | the budget | below the band it fails (Ver. 4.1) |
Observation 7.2 The four are not parallel. The first two are facts about the world, the third is a decision of ours, and the fourth is a resource. Saying “compressed sensing needs few measurements for a sparse signal” names one of the four.
Observation 7.3 Paper 163's sequence grows by one. Classification lists the classes (Paper 185), existence says a class is not empty, choice settles which member to take, and construction hands one over. The one-norm here is a rule of choice and ADMM is the construction.
8. Conclusion
- The system really is underdetermined (Ver. 2.1): a null space of dimension twelve.
- The norm decides the answer (Ver. 3.1): $2.2\times10^{-16}$ against $0.940$.
- The norm is necessary and not sufficient (Ver. 3.3): the one-norm misses by $0.837$ when the budget is short.
- The transition is narrow (Ver. 4.1): $0.400$ at seven nonzeros and $0$ at thirteen, on twenty measurements.
- Sparsity is the signal's and spread is the measurement's (Ver. 5.1): $40/40$ against $7/40$.
- A new tool is tried first where the answer is known (Obs. 6.2).
References
- Chen, S. S., Donoho, D. L., Saunders, M. A. (1998). Atomic Decomposition by Basis Pursuit. SIAM Journal on Scientific Computing, 20(1).
- Candès, E. J., Romberg, J., Tao, T. (2006). Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information. IEEE Transactions on Information Theory, 52(2).
- Donoho, D. L. (2006). Compressed Sensing. IEEE Transactions on Information Theory, 52(4).
- Candès, E. J., Tao, T. (2005). Decoding by Linear Programming. IEEE Transactions on Information Theory, 51(12).
- Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J. (2011). Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends in Machine Learning, 3(1).
- Yamagishi, Y. (2026). Reading the Interior from the Boundary [Paper 99]. Zenodo. 10.5281/zenodo.21758790
- Yamagishi, Y. (2026). Extracting Signal from Noise [Paper 106]. Zenodo. 10.5281/zenodo.21836984
- Yamagishi, Y. (2026). “Ill-Posed” Is Not One Word [Paper 159]. Zenodo. 10.5281/zenodo.22092229
- Yamagishi, Y. (2026). “A Good Code Exists” and “Here Is a Good Code” Are Different Sentences [Paper 163]. Zenodo. 10.5281/zenodo.22092677
- Yamagishi, Y. (2026). The Fence around Least Squares Is Linearity, Not Normality [Paper 171]. Zenodo. 10.5281/zenodo.22094287
- Yamagishi, Y. (2026). “Small” Is Two Words [Paper 176]. Zenodo. 10.5281/zenodo.22097994
- Yamagishi, Y. (2026). “The Curse of Dimensionality” Is Not One Curse [Paper 182]. Zenodo. 10.5281/zenodo.22104170
- Yamagishi, Y. (2026). What Classifies a Defect Is the Target Space [Paper 185]. Zenodo. 10.5281/zenodo.22105496
- Yamagishi, Y. (2026). When a Proxy Becomes the Target It Stops Being a Proxy [Paper 186]. Zenodo. 10.5281/zenodo.22105530
- Yamagishi, Y. (2026). The Gaussian Is Special for More Than One Reason [Paper 187]. Zenodo. 10.5281/zenodo.22105639
Reference
Yamagishi, Y. (2026). Fewer Measurements Than Unknowns, and Still Exact [Paper 188]. YOI: https://www.yamagishiyuuki.com/yoi/188
DOI: 10.5281/zenodo.22105691
ORCID: 0009-0006-8587-3450
PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS
The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 188. This paper is a preprint and has not been peer reviewed.