Penalized 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 penalty ${\tau }^2\ge 0$.

List all supports $S\subseteq \{1,\dots ,d\}$ in lexicographic order of their length-$d$ indicator vectors, using $0<1$. For each $S$, let $V_S$ be the span of the corresponding columns of $X$, compute ${\widehat{\mu }}_S=P_{V_S}y$, and score

$q_S:=n^{-1}\mathrm{\parallel }y-{\widehat{\mu }}_S{\mathrm{\parallel }}_2^2+{\tau }^2\mathrm{\mid }S\mathrm{\mid }\mathrm{.}$

Initialize the incumbent at the first support and scan the rest in order, replacing it exactly when a strictly smaller score is found; on a tie retain the earlier support. Return the selected support $\widehat{S}$ and fitted vector ${\widehat{\mu }}_{\mathrm{B}\mathrm{I}\mathrm{C}}={\widehat{\mu }}_{\widehat{S}}$. The candidate family is finite by $\mid \mathcal{P}(A)\mid =2^{\mid A\mid }$ for finite $A$, and the fitted-vector selection is Borel measurable by Finite tie-broken projection searches are Borel measurable. This is an exhaustive combinatorial procedure, not an efficiency guarantee.