High-dimensional scaling and geometric obstructions

Consider a fixed-design linear model with $n$ observations, $p$ coefficients, and mean-zero noise. If $p>n$, the design has a nontrivial null space. Adding any vector in that null space to the coefficient leaves the entire response distribution unchanged when the noise law is fixed. Thus unrestricted coefficient identification is impossible, even before considering computational cost. An optimization algorithm can choose a representative of the equivalence class, but its choice does not manufacture information about a direction absent from the observations.

Prediction error on the training design measures the image of the coefficient error, whereas coefficient error measures the vector itself. The former can vanish along an arbitrarily large null-space displacement. A new covariate vector can detect that displacement if it has a component in an unobserved direction. This is why interpolation alone is not a guarantee of reliable extrapolation. A minimum-norm solution, a sparse solution, and a scientifically constrained solution can agree perfectly on the data while making different claims about unseen inputs.

Sparsity restricts the parameter to vectors with at most a specified number of nonzero entries. Identification then asks whether two such vectors can have the same image. Their difference has at most twice as many nonzero entries, so uniqueness is equivalent to excluding nonzero null vectors with that doubled sparsity. This is weaker than requiring full column rank, yet stronger than checking that no single column is zero. Repeated or proportional columns already obstruct even some one-coordinate explanations.

There are many possible supports. A support of size $s$ has roughly $s\log(ep/s)$ units of combinatorial complexity, since the number of possible supports is bounded by $(ep/s)^s$. This expression helps explain sample-size scales in sparse estimation, but it is not a universal success theorem by itself. The design must distinguish the relevant directions, and sufficiently small signals can remain undetectable despite favorable sample size. Approximate sparsity also introduces an approximation error rather than granting exact identification automatically.

A single Gaussian noise coordinate averaged across observations has standard deviation proportional to the reciprocal square root of sample size. Searching across many coordinates introduces a maximum instead of one predetermined coordinate. A union bound over Gaussian tails gives the displayed simultaneous threshold without requiring independence between the coordinates. Its logarithmic dimension term is the price of asking one event to cover every candidate. Bounds for a fixed coordinate and bounds after searching must therefore be distinguished explicitly.

A useful asymptotic statement specifies sequences rather than saying merely that the sample becomes large. For example, a sparse-regression error scale proportional to $s\log p/n$ can vanish along one sequence of dimensions and fail along another. This differs from ordinary fixed-dimensional consistency. Likewise, random-design conclusions average over or condition on a design distribution, while a deterministic-design theorem must state a geometric condition on the realized matrix. Keeping these choices explicit prevents statistical and algebraic obstructions from being hidden inside an informal large-sample claim.