By my understanding, for a matrix with n samples and p features:

• Ridge regression using cholesky takes O(p^3) time
• Ordinary linear regression takes O(p^3) time
• Singular value decomposition if u, v and s are required takes O(p^3) time, but only takes O(np^2) time if u and v are not required

I tested this out in scipy on both random and real-world data with p > n (p = 43624, n = 1750) and found ridge regression to be much quicker than ordinary linear regression and SVD. Why is this?

import numpy as np
from sklearn import linear_model
import scipy
import time

x = np.random.rand(1750, 43264)
y = np.random.rand(1750)

old_time = time.time()
clf = linear_model.Ridge(alpha=1.0, solver='cholesky')
clf.fit(x, y)
print("Time taken to solve Ridge with cholesky: ", time.time() - old_time)

old_time = time.time()
clf = linear_model.LinearRegression()
clf.fit(x, y)
print("Time taken to solve linear regression: ", time.time() - old_time)

old_time = time.time()
scipy.linalg.svd(x, full_matrices=False)
print("Time taken for SVD", time.time() - old_time)

old_time = time.time()
scipy.linalg.svd(x, full_matrices=False, compute_uv=False)
print("Time taken for SVD, just s", time.time() - old_time)

Output:

Time taken to solve Ridge with cholesky:  3.339338541030884
Time taken to solve linear regression:  51.32710242271423
Time taken for SVD 65.02127623558044
Time taken for SVD, just s 25.550649881362915