Pith. sign in

REVIEW 3 major objections 5 minor 24 references

Comparing the Moore-Penrose Pseudoinverse and Gradient Descent for Solving Linear Regression Problems: A Performance Analysis

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper concludes that for linear regression on small and moderate datasets, the Moore–Penrose pseudoinverse beats batch gradient descent on both runtime and accuracy, with the edge widest on ill-conditioned data.

desk verdict A clean but textbook-level comparison; the fixed learning rate is a real weakness, but the qualitative conclusion about conditioning is not an artifact. read the letter →

arxiv 2505.23552 v1 pith:COVMSKN5 submitted 2025-05-29 cs.LG

Alex Adams This is my paper
classification cs.LG MSC 62J0565F20
keywords Moore-Penrosepseudoinversegradientdescentlinearregressionordinaryleastsquaresconditionnumbersingularvaluedecompositionsolverselectionnumericalstability
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish a practical rule for choosing a linear-regression solver: when the dataset is small to moderate—the tests run up to $n=5000$ samples and $d=50$ features—the closed-form Moore–Penrose pseudoinverse is generally preferable to batch gradient descent. In every tested configuration the pseudoinverse was orders of magnitude faster and reached stable, near-noise-floor error even when the feature matrix was badly conditioned, where gradient descent with a fixed learning rate either crawled or failed to converge. The paper explains the gap through two mechanisms: the pseudoinverse solves the ordinary least squares problem exactly in one SVD-based matrix operation whose cost is $O(nd^2 + d^3)$, while gradient descent's runtime is $O(k \cdot nd)$ and its required iteration count $k$ grows sharply with the condition number of $X^T X$. The documented boundary matters to practitioners because it supplies a concrete default—reach for the direct solver first, and reserve iterative methods for scales where forming the normal equations or an SVD becomes prohibitive.

What carries the argument

The central object is the Moore–Penrose pseudoinverse $X^+ = V\Sigma^+ U^T$, built from the singular value decomposition of the feature matrix, which delivers the minimum-norm least squares solution $\hat{\beta} = X^+ y$ in a single closed-form matrix operation. It carries the argument because it is exact, requires no hyperparameter tuning, and its SVD-based computation stays numerically stable when the normal-equations matrix $X^T X$ is ill-conditioned. Against it, the paper sets the convergence mechanism of batch gradient descent: for the quadratic OLS objective, the iteration count is governed by the condition number $\kappa(X^T X)$, so a narrow, elongated loss surface makes a fixed-step first-order method slow or divergent, and each iteration costs $O(nd)$. The two complexity identities—$O(nd^2 + d^3)$ for the pseudoinverse against $O(k \cdot nd)$ for gradient descent—supply the paper's regime boundary.

What would settle it

On the same synthetic protocol, run batch gradient descent on the ill-conditioned problems ($\mathrm{cond}=0.001$, $d=50$) with a learning rate chosen per problem—for instance a grid over $\alpha \in \{0.1, 0.01, 0.001, 0.0001\}$ or a value scaled below the spectral bound of $X^T X$—and record the best error within the 10,000-iteration budget; if tuned gradient descent reaches error near $0.01$ on configurations where the paper reports error near $55$, the blanket conclusion that the pseudoinverse is generally preferable would need qualification to 'preferable under a fixed, untuned step size.'

Watch

Extended reading notes

Core claim

The central claim is that the Moore–Penrose pseudoinverse is the preferred method for ordinary least squares regression on datasets of small to moderate size, where neither $n$ nor $d$ is excessively large. Empirically, on synthetic data with $n \in \{1000, 5000\}$, $d \in \{10, 50\}$, and condition factors of $1.0$ and $0.001$, the pseudoinverse solved every problem in milliseconds with mean squared error near the noise floor ($\mathrm{err_{pinv}} \approx 0.009$–$0.010$), whereas batch gradient descent took between roughly $0.1$ and $8.2$ seconds and, on ill-conditioned data, finished with average error as large as $55.15$ (and single-run errors above $57$) after exhausting its 10,000-iteration budget. On the California Housing and Diabetes datasets the same pattern held: the pseudoinverse was faster and its accuracy did not depend on preprocessing, while gradient descent's outcome was sensitive to feature scaling and learning-rate choices. The paper frames the result as a delineation of regimes rather than a universal ranking: for very large $n$, iterative methods—especially stochastic variants—are expected to become more practical because their per-iteration cost can be made independent of the dataset size, a regime the paper does not test directly.

Load-bearing premise

The load-bearing premise is that one fixed learning rate ($\alpha = 0.01$), settled by preliminary tuning rather than per dataset or per conditioning level, is a fair configuration for gradient descent in every comparison; if a step size chosen for each problem's conditioning lets gradient descent converge to similar error, the paper's blanket preference for the pseudoinverse would narrow.

Editorial extensions

If this is right

  • For regression problems within roughly the tested scale ($n$ up to 5000, $d$ up to 50), practitioners can treat the pseudoinverse as the default solver: it is faster and its accuracy does not depend on tuning a learning rate.
  • Ill-conditioned data is not, by itself, a reason to switch to iterating; under the paper's fixed-step settings the pseudoinverse stayed near the noise floor while gradient descent's average error on the hardest ill-conditioned group reached 55.15.
  • Gradient descent's role in the paper's account is reserved for very large $n$, where stochastic or mini-batch updates make the per-iteration cost independent of dataset size—a claim supported by complexity analysis rather than by direct experiment.
  • Choosing gradient descent on small or moderate data commits the modeler to feature scaling, regularization, or preconditioning to guard against conditioning failures, costs the pseudoinverse avoids.
  • The pseudoinverse's $O(d^3)$ SVD term means its advantage has an upper bound in dimensionality; the 'small to moderate' guidance marks exactly the range where that term is not yet dominant.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: because the comparison fixes one learning rate for all condition numbers, the cleanest reading is that the paper tests the pseudoinverse against untuned batch gradient descent; a step size chosen per problem, below the spectral bound of $X^T X$, would likely narrow the measured error gap on ill-conditioned data.
  • Editorial inference: the 'generally preferable' verdict is bounded to batch gradient descent; adaptive first-order methods, second-order methods, and randomized sketch-based approximations of the pseudoinverse sit outside the comparison, so the practical guidance may shift once those solvers are brought in.
  • Testable extension: sweeping $n$ well beyond 5000 and $d$ beyond 50 would turn the paper's asymptotic argument into a measured crossover point, which the discussion invokes but the experiments do not locate.
  • Testable extension: repeating the protocol with a per-conditioning learning-rate grid would separate the effect of data conditioning from the effect of step-size choice, and would tell practitioners exactly when tuning rescues gradient descent.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper compares the Moore–Penrose pseudoinverse with batch gradient descent for solving ordinary least squares linear regression. It reviews the theoretical underpinnings and computational complexity of both methods, then presents synthetic experiments varying sample size n (1000–5000), dimension d (10–50), and a 'condition factor' (1.0 or 0.001), together with an account of experiments on the California Housing and UCI Diabetes datasets. The central conclusion is that the pseudoinverse is 'generally preferable' for small-to-moderate datasets, being faster and more accurate, while gradient descent struggles on ill-conditioned data.

Significance. If fully supported, the paper would offer useful practical guidance for solver selection in linear regression. The theoretical complexity discussion is standard but clearly presented, and the synthetic-data design is a reasonable starting point for controlled comparison. However, the empirical support is not yet conclusive: the fixed learning rate for gradient descent, the absence of repeated trials or error bars, and the lack of reported results for the real-world datasets leave the central claim under-supported. The paper does not provide reproducible code, which further limits its practical impact. The contribution is modest but could be made sound with additional experiments.

major comments (3)
  1. [§3.1.2 and Table 1] The fixed learning rate α=0.01, with no reported sweep, is a load-bearing flaw in the comparison. All ill-conditioned rows in Table 1 hit the 10,000-iteration cap with large gradient-descent errors (err_gd from 7.63 to 57.43), but it is unknown whether a smaller or larger step, or one chosen from the Lipschitz constant of the gradient, would have produced much lower error. The statement that α was 'determined through preliminary tuning' gives no details. Please run a learning-rate sweep over a logarithmic range for each (n, d, cond) configuration and report the best achievable gradient-descent error and runtime, or otherwise justify that α=0.01 is appropriate across all tested condition numbers.
  2. [§3.2] The real-world dataset experiments are described in the methodology but no quantitative results (runtimes, MSEs, condition numbers, or learning-rate choices) are reported anywhere in the paper. The assertion that 'the results from these real-world datasets were generally consistent with synthetic data trends' is therefore unverifiable. Please include the actual measurements or explicitly reword the claims to state that real-world validation was not presented.
  3. [§4.1, Tables 1–3] All runtime measurements appear to be single runs with no repeated trials, error bars, or statistical tests. The claim that the pseudoinverse is 'consistently faster by orders of magnitude' would be more credible if runtimes were averaged over multiple independent runs with standard deviations, particularly because some entries (e.g., time_pinv = 0.00067 vs. 0.00056 in the first two rows of Table 1) are within typical timer noise. The descriptive statistics in Table 2 aggregate across different parameter settings rather than across repeated trials, so they do not provide the needed variance information.
minor comments (5)
  1. [§3.1.1] The procedure for generating X with a prescribed condition factor is underspecified; please describe how the singular vectors are chosen (e.g., random orthogonal matrices) so that the experiments are reproducible.
  2. [§4.4, Figure 10] Figure 10 aggregates data from n=1000 and n=5000 without showing the underlying points or a clear legend; please plot the actual iteration counts from Table 1 or state explicitly which points correspond to which n.
  3. [§5] The conclusion's phrase 'generally preferable' is broader than the tested range (n ≤ 5000, d ≤ 50, two condition factors). Please temper the wording to something like 'for the tested range of small-to-moderate datasets' and discuss how the result is expected to extrapolate.
  4. [§3.2] The methodology says GD learning rates were 'tuned via cross-validation' for real data, but no values or procedure are given; please specify the range considered and the chosen values.
  5. [Code and Data Availability] The code is stated to be 'available upon request'; making it publicly available would greatly improve reproducibility and is recommended.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the empirical comparison is self-contained and the conclusions rest on direct measurements, not on fitted inputs or self-citations.

full rationale

The paper makes no claim that a quantity is derived from first principles and then reused as an input; its central empirical result is a direct runtime and MSE comparison between the pseudoinverse and batch gradient descent on synthetic and real datasets. The pseudoinverse error and gradient descent error are measured independently from the same data-generation process, and neither quantity is defined in terms of the other. The learning rate alpha = 0.01 is stated as a fixed, preliminarily tuned hyperparameter, not fit to the specific test configurations in a way that would force the observed gradient-descent failures; the paper also reports iteration counts and stopping criteria transparently, so the ill-conditioned results are experimental observations rather than construction-level equivalences. The theoretical background is cited from standard textbooks and external references, with no load-bearing self-citation. The main weakness, that a single learning rate and a 10,000-iteration cap may understate gradient descent's capabilities on ill-conditioned problems, is a methodological fairness concern about the comparison, not a circularity in the derivation. Accordingly, no circular step satisfies the required standard of exhibiting an equation or fitted parameter that reduces to the paper's own inputs.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new entities. It relies on standard assumptions of linear regression and optimization. The only chosen hyperparameter is the learning rate, which is manually set and not fitted to data, but it is a free choice that affects the results.

free parameters (1)
  • learning rate alpha = 0.01
    Chosen via preliminary tuning and fixed for all experiments. This choice directly affects gradient descent convergence, especially on ill-conditioned data, but is not tuned per dataset or condition number.
assumptions (3)
  • domain assumption The linear regression model y = X beta + epsilon with i.i.d. Gaussian noise is appropriate for the data.
    Used in Section 2.1 to formulate the OLS problem and in Section 3.1.1 to generate synthetic data with known ground truth beta* = 1.
  • standard math The Moore-Penrose pseudoinverse computed via SVD is numerically stable and provides the minimum-norm least squares solution.
    Invoked in Section 2.2 and used in experiments via numpy.linalg.pinv; this is a standard result from linear algebra.
  • standard math Gradient descent convergence rate for quadratic objectives depends on the condition number of the Hessian X^T X.
    Stated in Section 4.4 and used to interpret the empirical results; this is a standard result in optimization theory.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Comparing the Moore-Penrose Pseudoinverse and Gradient Descent for Solving Linear Regression Problems: A Performance Analysis." pith.science (2026). https://pith.science/paper/COVMSKN5

@misc{pith2026250523552,
  author       = {Pith},
  title        = {Pith review of: Comparing the Moore-Penrose Pseudoinverse and Gradient Descent for Solving Linear Regression Problems: A Performance Analysis},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/COVMSKN5}},
  note         = {Machine review of arXiv:2505.23552}
}
read the original abstract

This paper investigates the comparative performance of two fundamental approaches to solving linear regression problems: the closed-form Moore-Penrose pseudoinverse and the iterative gradient descent method. Linear regression is a cornerstone of predictive modeling, and the choice of solver can significantly impact efficiency and accuracy. I review and discuss the theoretical underpinnings of both methods, analyze their computational complexity, and evaluate their empirical behavior on synthetic datasets with controlled characteristics, as well as on established real-world datasets. My results delineate the conditions under which each method excels in terms of computational time, numerical stability, and predictive accuracy. This work aims to provide practical guidance for researchers and practitioners in machine learning when selecting between direct, exact solutions and iterative, approximate solutions for linear regression tasks.

Figures

Figures reproduced from arXiv: 2505.23552 by the authors.

Figure 1
Figure 1. Conceptual illustration of linear regression, showing data points (blue dots) and the [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Conceptual illustration of gradient descent. The contours represent the level sets [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Visual comparison of loss surfaces for well-conditioned (left, more spherical contours) [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Runtime (seconds) vs. Number of Features (d) for the Moore-Penrose Pseudoinverse [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: Runtime (seconds) vs. Number of Features (d) for the Gradient Descent method with [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: Runtime (seconds) vs. Number of Samples (n) for the Moore-Penrose Pseudoinverse [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: Runtime (seconds) vs. Number of Samples (n) for the Gradient Descent method with [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 8
Figure 8. Figure 8: Mean Squared Error (MSE) vs. Number of Features (d) for the Moore-Penrose [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]
Figure 9
Figure 9. Figure 9: Mean Squared Error (MSE) vs. Number of Features (d) for the Gradient Descent [PITH_FULL_IMAGE:figures/full_fig_p013_9.png]
Figure 10
Figure 10. Figure 10: Gradient Descent Iterations vs. Conditioning Factor for experiments with [PITH_FULL_IMAGE:figures/full_fig_p014_10.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

24 extracted references · 21 canonical work pages

  1. [1]

    Albert, A. (1972). Regression and the Moore-Penrose Pseudoinverse . Academic Press

    work page 1972

  2. [2]

    Ben-Israel, A., & Greville, T. N. E. (2003). Generalized Inverses: Theory and Applications (2nd ed.). Springer

    work page 2003

  3. [3]

    Bishop, C. M. (2006). Pattern Recognition and Machine Learning . Springer

    2006

  4. [4]

    Bottou, L. (2010). Large-scale machine learning with stochastic gradient descent. In Pro- ceedings of COMPSTAT’2010 (pp. 177-186). Physica-Verlag HD

    work page 2010

  5. [5]

    Boyd, S., & Vandenberghe, L. (2004). Convex Optimization . Cambridge University Press

    work page 2004

  6. [6]

    Cauchy, A. (1847). M´ ethode g´ en´ erale pour la r´ esolution des syst` emes d’´ equations simul- tan´ ees.Comp. Rend. Acad. Sci. Paris , 25, 536-538

    work page

  7. [7]

    Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004). Least angle regression. The Annals of Statistics , 32(2), 407-499. 16

    work page 2004

  8. [8]

    Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep Learning. MIT Press

    work page 2016

Show all 24 references
  1. [9]

    H., & Van Loan, C

    Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press

    2013

  2. [10]

    Hand, D. J. (1996). Statistics and the theory of measurement. Journal of the Royal Statis- tical Society: Series A (Statistics in Society) , 159(3), 445-492

    1996

  3. [11]

    Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer

    2009

  4. [12]

    E., & Kennard, R

    Hoerl, A. E., & Kennard, R. W. (1970). Ridge regression: Biased estimation for nonorthog- onal problems. Technometrics, 12(1), 55-67

    1970

  5. [13]

    P., & Ba, J

    Kingma, D. P., & Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980

    2014 arXiv

  6. [14]

    Mahoney, M. W. (2011). Randomized algorithms for matrices and data. Foundations and Trends® in Machine Learning , 3(2), 123-224

    2011

  7. [15]

    C., Peck, E

    Montgomery, D. C., Peck, E. A., & Vining, G. G. (2021). Introduction to Linear Regression Analysis (6th ed.). Wiley

    2021

  8. [16]

    Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer

    2006

  9. [17]

    K., & Barry, R

    Pace, R. K., & Barry, R. (1997). Sparse spatial autoregressions. Statistics & Probability Letters, 33(3), 291-297

    1997

  10. [18]

    Penrose, R. (1955). A generalized inverse for matrices. Mathematical Proceedings of the Cambridge Philosophical Society , 51(3), 406-413

    1955

  11. [19]

    Ruder, S. (2016). An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04747

    2016 arXiv

  12. [20]

    Saad, Y. (2003). Iterative Methods for Sparse Linear Systems (2nd ed.). SIAM

    2003

  13. [21]

    Seber, G. A. F., & Lee, A. J. (2003). Linear Regression Analysis (2nd ed.). Wiley

    2003

  14. [22]

    N., & Bau III, D

    Trefethen, L. N., & Bau III, D. (1997). Numerical Linear Algebra. SIAM

    1997

  15. [23]

    Weisberg, S. (2005). Applied Linear Regression (3rd ed.). Wiley

    2005

  16. [24]

    Woodruff, D. P. (2014). Sketching as a tool for numerical linear algebra. Foundations and Trends® in Theoretical Computer Science , 10(1–2), 1-157. 17

    2014

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.