Least Squares

Author

Anqi Fu and Balasubramanian Narasimhan

Introduction

In a least-squares, or linear regression, problem, we have measurements \(A \in \mathcal{R}^{m \times n}\) and \(b \in \mathcal{R}^m\) and seek a vector \(x \in \mathcal{R}^{n}\) such that \(Ax\) is close to \(b\). Closeness is defined as the sum of the squared differences:

\[ \sum_{i=1}^m (a_i^Tx - b_i)^2, \]

also known as the \(\ell_2\)-norm squared, \(\|Ax - b\|_2^2\).

For example, we might have a dataset of \(m\) users, each represented by \(n\) features. Each row \(a_i^T\) of \(A\) is the features for user \(i\), while the corresponding entry \(b_i\) of \(b\) is the measurement we want to predict from \(a_i^T\), such as ad spending. The prediction is given by \(a_i^Tx\).

We find the optimal \(x\) by solving the optimization problem

\[ \begin{array}{ll} \mbox{minimize} & \|Ax - b\|_2^2. \end{array} \]

Let \(x^\star\) denote the optimal \(x\). The quantity \(r = Ax^\star - b\) is known as the residual. If \(\|r\|_2 = 0\), we have a perfect fit.

Example

In the following code, we solve a least-squares problem with CVXR.

## Generate data
set.seed(1)
m <- 20
n <- 15
A <- matrix(rnorm(m * n), nrow = m, ncol = n)
b <- rnorm(m)

## Define and solve the CVXR problem
x <- Variable(n)
cost <- sum_squares(A %*% x - b)
prob <- Problem(Minimize(cost))
result <- psolve(prob)
check_solver_status(prob)
## Print result
cat(sprintf("The optimal value is %f\n", result))
cat("The optimal x is\n")
print(value(x))
cat(sprintf("The norm of the residual is %f\n",
            value(norm2(A %*% x - b))))
Warning: `norm2()` is deprecated. Use `p_norm(x, 2)` instead.
This warning is displayed once per session.
The optimal value is 3.803864
The optimal x is
              [,1]
 [1,]  0.777895927
 [2,]  0.355140233
 [3,]  1.012870340
 [4,]  1.235069182
 [5,]  0.495428315
 [6,]  0.213417121
 [7,]  0.583166521
 [8,] -0.006304388
 [9,]  0.100449253
[10,]  1.457467770
[11,] -0.187239012
[12,]  0.018858706
[13,] -1.083027349
[14,]  1.717597206
[15,]  0.988668997
The norm of the residual is 1.950350

Session Info

R version 4.5.3 (2026-03-11)
Platform: aarch64-apple-darwin20
Running under: macOS Tahoe 26.3.1

Matrix products: default
BLAS:   /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRblas.0.dylib 
LAPACK: /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRlapack.dylib;  LAPACK version 3.12.1

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

time zone: America/Los_Angeles
tzcode source: internal

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] CVXR_1.8.1

loaded via a namespace (and not attached):
 [1] slam_0.1-55       cli_3.6.5         knitr_1.51        ECOSolveR_0.6.1  
 [5] rlang_1.1.7       xfun_0.56         clarabel_0.11.2   otel_0.2.0       
 [9] gurobi_13.0-1     Rglpk_0.6-5.1     highs_1.12.0-3    cccp_0.3-3       
[13] scs_3.2.7         S7_0.2.1          jsonlite_2.0.0    backports_1.5.0  
[17] rprojroot_2.1.1   htmltools_0.5.9   Rmosek_11.1.1     gmp_0.7-5.1      
[21] piqp_0.6.2        rmarkdown_2.30    grid_4.5.3        evaluate_1.0.5   
[25] fastmap_1.2.0     yaml_2.3.12       compiler_4.5.3    codetools_0.2-20 
[29] htmlwidgets_1.6.4 Rcpp_1.1.1        here_1.0.2        osqp_1.0.0       
[33] lattice_0.22-9    digest_0.6.39     checkmate_2.3.4   Matrix_1.7-4     
[37] tools_4.5.3

References