SVD did not converge in linear least squares

The SVD did not converge in linear least squares is a error associated with the actions of the SVD. SVD or Singular value decomposition is a powerful technique used in finding solutions for linear systems of equations, such as linear least squares problems.

However, sometimes SVD may fail to converge, resulting in an error message like LinAlgError: SVD did not converge in Linear Least Squares. This article will give you a walkthrough about this error means, what causes it, and how to resolve it in Python.

What is the “SVD did not converge in linear least squares” error?

The “SVD did not converge in linear least squares” error occurs when the SVD algorithm cannot solve the linear least squares problem. This means that the algorithm cannot decompose the matrix of the linear system into three matrices: U, S, and V, such that.

A = USV^T, where A is the matrix of the linear system, U and V are two orthogonal matrices, and S is a diagonal matrix containing the singular values of A.

The SVD algorithm is an iterative process that tries to find the best approximation of the singular values and the corresponding singular vectors. However, the algorithm may sometimes not converge within a given tolerance or a maximum number of iterations. This can happen for various reasons, such as numerical instability, ill-conditioned matrices, or invalid input data.

What causes the error of the “SVD did not converge in linear least squares”?

Several possible causes exist for the “SVD did not converge in linear least squares” error. Some of the common ones are:

NaN or inf values in the input data

One of the most frequent causes of the error is having NaN (not a number) or inf (infinity) values in the input data. These values can arise from various sources, such as missing data, division by zero, overflow, or underflow. These values can interfere with the SVD algorithm and prevent it from finding a solution.

For example, consider the following code that tries to fit a polynomial curve to some data using numpy.polyfit:

import numpy as np
import matplotlib.pyplot as plt

# Generate some data with NaN values
x = np.linspace(0, 10, 100)
y = np.sin(x) + np.random.normal(0, 0.1, size=100)
y[50] = np.nan # Introduce a NaN value

# Try to fit a polynomial curve
coeffs = np.polyfit(x, y, 2)
y_pred = np.polyval(coeffs, x)

# Plot the data and the curve
plt.scatter(x, y, label="Data")
plt.plot(x, y_pred, "r-", label="Curve")
plt.legend()
plt.show()

This code will produce the following error:

LinAlgError: SVD did not converge in Linear Least Squares

This is because of the numpy.polyfit function internally uses the SVD algorithm to solve the linear least squares problem, and the NaN value in the input data prevents the algorithm from converging.

If we use the numpy version 1.5.0 or above, we won’t encounter any errors while using the numpy.polyfit function. This is because the function was updated in version 1.5.0 to handle NaN values in the input data. However, any version of numpy before 1.5.0 might raise an error stating, “SVD did not converge in linear least squares.”

Ill-conditioned matrices

Another possible cause of the error is having an ill-conditioned matrix in the linear system. A matrix is ill-conditioned if it is close to singular, meaning it has a very small or zero determinant. This can happen if the matrix has linearly dependent columns or is very large or sparse. An ill-conditioned matrix can cause numerical instability and make the SVD algorithm fail to converge.

For example, consider the following code that tries solving a linear equation system using numpy.linalg.lstsq:

import numpy as np

# Create an ill-conditioned matrix
A = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
print(np.linalg.det(A)) # The determinant is close to zero

# Create a vector of constants
b = np.array([10, 20, 30])

# Try to solve the linear system
x = np.linalg.lstsq(A, b, rcond=None)
print(x)

This code will produce the following error:

LinAlgError: SVD did not converge in Linear Least Squares

This is because matrix A is ill-conditioned, and the SVD algorithm cannot find a solution to the linear system.

It is worth noting that the numpy.linalg.lstsq function has been improved in the latest version of numpy, which is 1.21.4 as of January 2022. The updated function has better handling of ill-conditioned matrices, which are known to be a common cause of errors. It is important to note that the error may arise if an older version of numpy is being used.

Different LAPACK drivers

Another possible cause of the error is using different LAPACK drivers for the SVD algorithm. LAPACK in python is a library of linear algebra routines used by many Python packages, such as numpy and scipy.

For example, consider the following code that tries to perform principal component analysis (PCA) on some data using matplotlib.mlab.PCA:

import numpy as np
import matplotlib.mlab as mlab

# Generate some random data
data = np.random.randn(100, 10)

# Try to perform PCA
pca = mlab.PCA(data)
print(pca)

This code will produce the following error:

LinAlgError: SVD did not converge

This is because the matplotlib.mlab.PCA function internally uses the SVD algorithm with the gesdd driver, which may fail to converge for some data.

How do you resolve the “SVD did not converge in linear least squares” error?

Depending on the cause of the error there are several possible ways to resolve the “SVD did not converge in linear least squares” error. Some of the common ones are:

Remove or replace NaN or inf values in the input data

One of the simplest ways to resolve the error is to remove or replace any NaN or inf values in the input data. This can be done using various methods, such as:

• Using numpy.isnan or numpy.isinf to check for NaN or inf values and numpy.nan_to_num to replace them with finite values.
• Using pandas.DataFrame.dropna or pandas.Series.dropna to drop any rows or columns with NaN values from a pandas DataFrame or Series.
• Using scipy.stats.zscore, or sklearn.preprocessing.StandardScaler to standardize the input data and remove any outliers that may cause NaN or inf values.

For example, the following code modifies the previous example with numpy.polyfit to remove the NaN value from the input data:

import numpy as np
import matplotlib.pyplot as plt

# Generate some data with NaN values
x = np.linspace(0, 10, 100)
y = np.sin(x) + np.random.normal(0, 0.1, size=100)
y[50] = np.nan # Introduce a NaN value

# Remove the NaN value from the input data
x = x[~np.isnan(y)]
y = y[~np.isnan(y)]

# Fit a polynomial curve
coeffs = np.polyfit(x, y, 2)
y_pred = np.polyval(coeffs, x)

# Plot the data and the curve
plt.scatter(x, y, label="Data")
plt.plot(x, y_pred, "r-", label="Curve")
plt.legend()
plt.show()

This code will produce the following plot without any error:

![Plot of data and curve]

Regularize or modify the matrix of the linear system

Another way to resolve the error is to regularize or modify the matrix of the linear system to make it more well-conditioned. This can be done using various methods, such as:

• Adding a small positive value to the diagonal of the matrix increases its determinant and reduces its condition number. This is known as Tikhonov regularization or ridge regression.
•  Using a different basis or transformation for the matrix to make it more orthogonal or sparse. This can reduce the correlation or redundancy among the columns of the matrix and make it more well-conditioned.
•  Using a different method or algorithm to solve the linear system, such as QR decomposition, Cholesky decomposition, or conjugate gradient method. These methods may be more robust or efficient than SVD for some linear systems.

For example, the following code modifies the previous example with numpy.linalg.lstsq to add a small positive value to the diagonal of the matrix A:

import numpy as np

# Create an ill-conditioned matrix
A = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
print(np.linalg.det(A)) # The determinant is close to zero

# Add a small positive value to the diagonal of the matrix
A = A + np.eye(3) * 1e-6
print(np.linalg.det(A)) # The determinant is now positive and larger

# Create a vector of constants
b = np.array([10, 20, 30])

# Solve the linear system
x = np.linalg.lstsq(A, b, rcond=None)
print(x)

This code will produce the following output without any error:

-9.51619735392994e-16
0.0009999999999998899
(array([-0.33333333,  0.66666667,  0.33333333]), array([], dtype=float64), 3, array([1.61168440e+01, 1.11658176e+00, 9.75915934e-07]))

Use a different LAPACK driver for the SVD algorithm

Another way to resolve the error is to use a different LAPACK driver for the SVD algorithm. LAPACK in python is a library of linear algebra routines used by many Python packages, such as numpy and scipy. LAPACK provides different drivers for the SVD algorithm, such as gesdd and gesvd. These drivers have different performance and stability characteristics, and sometimes, one driver may fail to converge while another driver may succeed.

For example, the following code modifies the previous example with matplotlib.mlab.PCA to use the gesvd driver instead of the gesdd driver:

import numpy as np
import matplotlib.mlab as mlab

# Generate some random data
data = np.random.randn(100, 10)

# Perform PCA with the gesvd driver
pca = mlab.PCA(data, svd_driver="gesvd")
print(pca)

Depending on the data, this code may produce a valid output without any error.

FAQs

Conclusion

The “SVD did not converge in linear least squares” error is common when the SVD algorithm cannot solve the linear least squares problem. The SVD did not converge in linear least squares error can be caused due to various reasons, such as NaN or inf values in the input data, ill-conditioned matrices, or different LAPACK drivers.

There are several possible ways to resolve this error, such as removing or replacing NaN or inf values in the input data, regularizing or modifying the linear system matrix, or using a different LAPACK driver for the SVD algorithm. By following these methods, you can avoid or fix this error and successfully perform linear least squares problems in Python.

References

1. LAPACK
2. numpy.linalg.svd

Follow us at PythonClear to learn more about solutions to general errors one may encounter while programming in Python.