Constrained support-search least squares

Input: naturals $n,d\ge 1$, a fixed design $X\in {\mathbb{R}}^{n\times d}$, a data vector $y\in {\mathbb{R}}^n$, and a natural $s$ with $0\le s\le d$.

Candidate supports: list all subsets $S\subseteq \{1,\dots ,d\}$ with $\mathrm{\mid }S\mathrm{\mid }\le s$ in lexicographic order of their length-$d$ indicator vectors, using $0<1$. This is a finite nonempty list because it contains $\mathrm{\varnothing }$ and is contained in the finite power set of $\{1,\dots ,d\}$.

Procedure: for each candidate $S$, let $V_S$ be the span of the columns of $X$ indexed by $S$ and compute ${\widehat{\mu }}_S=P_{V_S}y$. Compute its residual score $q_S=\mathrm{\parallel }y-{\widehat{\mu }}_S{\mathrm{\parallel }}_2^2$. Initialize the incumbent at the first candidate. Scan the remaining candidates in the stated order, replacing the incumbent exactly when a strictly smaller score is found; retain the earlier candidate on a tie. Return the selected support and its fitted vector ${\widehat{\mu }}_s$.

Each $V_S$ is finite-dimensional, so the projections are defined by Fixed-design least squares as orthogonal projection. The fitted-vector selection is Borel measurable by Finite tie-broken projection searches are Borel measurable. The procedure performs a finite exhaustive support search; no computational-efficiency claim is made.