Home / Curated / Algorithms / Orthogonal least squares forward selection

Orthogonal least squares forward selection

Algorithms AIMech:OrthogonalLeastSquaresForwardSelection DRAFT

Aliases: Forward regression orthogonal least squares, FROLS

A greedy fixed-candidate regression algorithm that repeatedly adds the column giving the largest reduction in squared residual after joint least-squares refitting over the augmented selected span.

Identity Notes & Concept Scope All 442 pinned AIO IDs, labels and scoped synonyms and 527 native IDs, names and aliases were compared with the proposed full names and OLS/OFR/FROLS terms, with no normalized identity match. Ignored- and hidden-inclusive full-text searches of the independent public clone and the readable prior worktree returned 37 and 12 lines, all inspected. Hits concern this source lead, historical OMP review boundaries, ordinary least-squares proposals, Ontology Lookup Service indexing, and ordinary orthogonal projection context. Bare OLS is not asserted as an alias because it also abbreviates ordinary least squares. The original Documents checkout remains inaccessible, so its untracked files were not re-audited in this round. All 62 semantic AIO rows and 82 native name/definition neighbors were read, followed by 12 full annotated AIO CLASS nodes with incident edges and 18 contextual YAMLs. The algorithm differs from OMP’s raw-correlation selection, MP’s single-atom update, exact minimum-L1 basis pursuit, the LARS equiangular path, and PLS/supervised-PCA component fitting. The new recovery worktree has the verified merged public tree. This is a bounded corpus assessment.

Claims & Grounded Evidence

7 Claims

Mechanism #forward-selection-and-refit

For a fixed finite real candidate matrix P and response y, start with an empty selected set S and residual y. For each unselected column p_j with nonzero residualized direction w_j=(I-Proj_S)*p_j, evaluate gain_j=(r^T*w_j)^2/(w_j^T*w_j). Choose a maximum-gain candidate, augment S and compute the least-squares fit over that span. This minimizes the residual sum of squares among single-column augmentations of the current S. The residual is orthogonal to the selected span in exact arithmetic. Original columns need not be orthogonal or unit length. Zero-gain termination and rank/zero-direction handling are necessary boundary conventions; they do not imply that y lies in the dictionary span.

supports Source: Orthogonal least squares methods and their application to non-linear system identification · Locator: Section 4, Equations 64–82, PDF pp. 13–18 / printed pp. 1884–1889
supports Source: On the Difference Between Orthogonal Matching Pursuit and Orthogonal Least Squares · Locator: Sections II–IV and VI, PDF pp. 2–3, March 29, 2007 draft

Mechanism #error-reduction-ratio

For nonzero y the source defines ERR_j=g_j^2*(w_j^T*w_j)/(y^T*y), where g_j=(w_j^T*y)/(w_j^T*w_j). Thus ERR is the incremental fitted energy divided by the original response energy. Orthogonality gives ||r_k||^2/||y||^2=1-sum_{i<=k} ERR_i. The denominator is uncentered energy despite the paper’s variance terminology: fitting a constant to y=(1,2) has ERR=9/10 while explaining none of the centered variation. Centered-variance interpretation needs appropriate centering/intercept conventions. The ratio is undefined at y=0, for which the zero fit already has zero error.

supports Source: Orthogonal least squares methods and their application to non-linear system identification · Locator: Section 4.1, Equations 64–70, and Section 4.2 Equation 74, PDF pp. 13–16 / printed pp. 1884–1887; curator exact calculations in research/discovery/orthogonal-least-squares-boundaries.py

Scope #omp-selection-distinction

OMP compares absolute residual correlations with the original unit atoms. OLS instead compares correlations with their normalized residualized directions; the different denominators can reverse the ranking. For D=[e1,b,e3], b=(12/13,5/13,0), y=(10,4/5,3/5), both first choose e1. OMP then chooses e3 because 3/5>4/13; OLS chooses b because its squared-error reduction 16/25 exceeds 9/25. The two-step residual energies are respectively 16/25 and 9/25. Both refit their chosen span, so refitting alone does not make the algorithms identical.

supports Source: On the Difference Between Orthogonal Matching Pursuit and Orthogonal Least Squares · Locator: Sections II–IV and VI, PDF pp. 2–3, March 29, 2007 draft; curator exact calculations in research/discovery/orthogonal-least-squares-boundaries.py
supports Source: Orthogonal least squares methods and their application to non-linear system identification · Locator: Section 4, Equations 64–82, PDF pp. 13–18 / printed pp. 1884–1889; curator exact calculations in research/discovery/orthogonal-least-squares-boundaries.py

Limitation #greedy-optimality-and-scaling

Best single augmentation is conditional on earlier selections and does not establish globally best subset selection or minimum support. For unit columns [e1,e2,e3,b], b=(8/9,4/9,1/9), and y=e1-b, exact forward OLS with lowest-index tie resolution selects e2,e1,e3 and uses three atoms for zero error. A two-atom representation e1-b exists and no one atom is collinear with y. In the ideal fixed-matrix unregularized procedure, nonzero rescaling of individual columns preserves the gain scores, selected subspaces and residuals under the same tie rule, though coefficient values change. Finite-precision tolerances and regularized variants need separate analysis.

supports Source: Orthogonal least squares methods and their application to non-linear system identification · Locator: Sections 2 and 4, PDF pp. 4–5,13–18 / printed pp. 1875–1876,1884–1889; curator exact calculations in research/discovery/orthogonal-least-squares-boundaries.py
supports Source: On the Difference Between Orthogonal Matching Pursuit and Orthogonal Least Squares · Locator: Sections II–IV and VI, PDF pp. 2–3, March 29, 2007 draft; curator exact calculations in research/discovery/orthogonal-least-squares-boundaries.py

Scope #stopping-and-numerical-variants

The paper implements the forward criterion through classical Gram-Schmidt, modified Gram-Schmidt and Householder transformations, with differing storage and roundoff behavior. Orthogonal decomposition is an implementation mechanism, not a requirement that the supplied features be orthogonal. It describes residual-energy tolerance, incremental criteria and penalized AIC-based stopping; none is an unconditional prediction or true-support guarantee. The mathematical rule and its implementation/stopping choices must be distinguished. No universal runtime superiority over OMP or other subset methods is asserted.

supports Source: Orthogonal least squares methods and their application to non-linear system identification · Locator: Sections 3.2 and 4, PDF pp. 8–18 / printed pp. 1879–1889
supports Source: On the Difference Between Orthogonal Matching Pursuit and Orthogonal Least Squares · Locator: Sections III and V, PDF pp. 2–3

Application #nonlinear-identification-boundary

A polynomial NARX model can be nonlinear in lagged observed inputs and outputs while remaining linear in its unknown coefficients, so its fixed candidate columns fit this selection procedure. Polynomial NARMAX identification additionally uses lagged noise terms that are not directly observed. The paper’s outer iterative scheme substitutes prediction residuals, rebuilds noise regressors and reestimates models; that changing-regressor extension is not a single fixed-matrix OLS pass and its reported iteration counts are not a convergence theorem. The fitted algorithm does not itself establish causal identification of a physical system.

supports Source: Orthogonal least squares methods and their application to non-linear system identification · Locator: Sections 2 and 5, Equations 1–13 and 83–91, PDF pp. 3–5,18–20 / printed pp. 1874–1876,1889–1891

Scope #frols-name-scope

The official SysIdentPy documentation expands FROLS as Forward Regression Orthogonal Least Squares and cites the Chen–Billings–Luo paper. This record uses that naming for the basic unregularized forward selection procedure. A software class with that name may expose other estimators or regularization options; its full configurable behavior is not asserted equivalent to this narrowly defined procedure.

supports Source: SysIdentPy documentation for FROLS · Locator: FROLS class heading, introductory description, source references and displayed constructor
supports Source: Orthogonal least squares methods and their application to non-linear system identification · Locator: Section 4, Equations 64–82, PDF pp. 13–18 / printed pp. 1884–1889

⚠️ Curated Limitations & Negative Results

The record covers finite real fixed-regressor, unregularized forward selection. Complex spaces, regularization, backward/floating revisions, multi-output joint selection and changing-noise-regressor estimation require their own evidence and conditions.
Zero response and zero/dependent candidate directions require explicit handling. Candidate construction, tie resolution, numerical rank and stopping affect the fitted subset; no universal support-recovery or out-of-sample guarantee is curated.
All 25 pages of the 1989 publisher PDF including its cover and all three pages of the 2007 draft were visually read. The current official documentation is nomenclature context only, not versioned implementation validation. Earlier cited methods and later variants are pending primary audits.
The source’s uncentered energy is not automatically centered variance. The apparent missing norm squares in Equation 44 are not used; the record uses the squared-energy identities of Section 4. No author erratum is claimed.
Exact rational examples are curator calculations. No empirical benchmark, author software, model training or paid provider was run. The record remains DRAFT and has no independent scientific approval.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:LeastsquaresAnalysis` Least-squares Analysis	related_match	The algorithm uses least-squares projection at every candidate augmentation, directly relating it to the target’s residual-squared fitting task. The pinned target describes overdetermined regression analysis, whereas this record denotes a specific greedy subset-selection algorithm and also allows overcomplete candidate sets. Related mapping preserves that algorithm/task and scope distinction; it is not exact identity or an asserted subclass.
`AIO:SparseLearning` Sparse Learning	related_match	The procedure seeks a parsimonious representation from supplied columns. The pinned target denotes a representation-learning network and identifies dictionary elements; the local algorithm neither requires a network nor learns those elements. Related mapping reflects sparse representation without treating this algorithm as dictionary learning. RepresentationLearning and SparseAutoEncoder are different neural scopes; LassoRegression and RidgeRegression do not specify this greedy gain criterion. LinearRegression and RegressionAnalysis describe fitting tasks, PLS and supervised PCA fit latent components, and FeatureExtraction is too general. RadialBasisNetwork and autoregressive model classes are potential model contexts, not identities for this selection rule.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`chen1989`	Orthogonal least squares methods and their application to non-linear system identification S. Chen, S. A. Billings, W. Luo	primary paper full_text	ID: https://doi.org/10.1080/00207178908953472 sha256:62199a403df8…
`blumensath2007`	On the Difference Between Orthogonal Matching Pursuit and Orthogonal Least Squares Thomas Blumensath, Mike E. Davies	author technical report full_text	sha256:5c62d9787b52…
`sysidentpy-naming`	SysIdentPy documentation for FROLS SysIdentPy developers	official documentation documentation	sha256:297aacc71869…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-12T12:45:27Z

Updated: 2026-10-12T12:45:27Z

Source File: data/curated/OrthogonalLeastSquaresForwardSelection.yaml