Least Squares

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^{T}x-b_i{)}^2,$$

also known as the ${\ell }_2$-norm squared, $\parallel Ax-b{\parallel }_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^{T}x$.

We find the optimal $x$ by solving the optimization problem

$$\begin{array}{ll}\text{minimize}& \parallel Ax-b{\parallel }_2^2.\end{array}$$

Let $x^{\star }$ denote the optimal $x$. The quantity $r=A{x}^{\star }-b$ is known as the residual. If $\parallel r{\parallel }_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.2 (2025-10-31)
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    Rcplex_0.3-8     
[17] backports_1.5.0   rprojroot_2.1.1   htmltools_0.5.9   Rmosek_11.1.1    
[21] gmp_0.7-5.1       piqp_0.6.2        rmarkdown_2.30    grid_4.5.2       
[25] evaluate_1.0.5    fastmap_1.2.0     yaml_2.3.12       compiler_4.5.2   
[29] codetools_0.2-20  htmlwidgets_1.6.4 Rcpp_1.1.1        here_1.0.2       
[33] osqp_1.0.0        lattice_0.22-9    digest_0.6.39     checkmate_2.3.4  
[37] Matrix_1.7-4      tools_4.5.2      

References