How do you choose the optimal rank for low-rank approximation?

1 What is low-rank approximation?

Low-rank approximation is the process of finding a matrix or tensor that has a lower rank than the original data, but is close to it in some sense. Rank is a measure of how many linearly independent rows or columns a matrix or tensor has. A lower rank means fewer degrees of freedom and less redundancy. For example, a rank-one matrix is just the outer product of two vectors, and a rank-one tensor is the product of three vectors. A low-rank approximation can capture the most important features or patterns of the data, while discarding the less relevant or noisy ones.

2 Why use low-rank approximation?

Low-rank approximation can offer several benefits for data processing and analysis. First, it can reduce the storage space and memory usage of the data, since a low-rank matrix or tensor has fewer entries than the original one. Second, it can speed up the computation and communication of the data, since a low-rank matrix or tensor can be manipulated more easily and efficiently than a full-rank one. Third, it can improve the accuracy and robustness of the data, since a low-rank matrix or tensor can filter out the noise or outliers that may affect the quality of the data.

3 How to measure approximation quality?

Low-rank approximation presents a challenge in measuring how well a low-rank matrix or tensor approximates the original data. To quantify the approximation quality, different measures can be used, depending on the goal and context of the problem. These include the Frobenius norm, which is the square root of the sum of squared differences between entries of the original and approximated matrices or tensors, and measures overall distance or error. The spectral norm, which is the largest singular value of the difference between original and approximated matrices or tensors, quantifies worst-case distortion or amplification of data by the approximation. The relative error is the ratio of the norm of the difference to the norm of the original data, measuring how much the approximation changes scale or magnitude. Lastly, there is the correlation coefficient, which is the cosine of angle between original and approximated matrices or tensors and measures how much approximation preserves direction or orientation of data.

4 How to perform low-rank approximation?

One of the most popular and versatile methods for performing low-rank approximation is the singular value decomposition (SVD). SVD is a mathematical technique that decomposes any matrix or tensor into three factors: a left singular matrix or tensor, a diagonal matrix or tensor of singular values, and a right singular matrix or tensor. The singular values are non-negative numbers that indicate the importance or contribution of each factor to the original data. The rank of the original matrix or tensor is equal to the number of non-zero singular values.

By truncating or discarding the smallest singular values and their corresponding factors, you can obtain a low-rank approximation of the original matrix or tensor. The rank of the approximated matrix or tensor is equal to the number of retained singular values. The SVD can guarantee that this approximation is optimal in terms of minimizing the Frobenius norm or the spectral norm of the difference.

5 How to choose the optimal rank?

When choosing the optimal rank for low-rank approximation, one must consider the trade-off between approximation quality and computational cost. A higher rank yields a better approximation, but also requires more storage, memory, and computation. Conversely, a lower rank yields a worse approximation, but also requires fewer resources. To select the optimal rank, one can use the elbow method to plot the singular values and look for an elbow point; the energy method to compute the ratio of the sum of the squared singular values; the error method to set a tolerance for the norm or relative error; or the cross-validation method to divide the original data into training and testing sets. Ultimately, one must select a rank that minimizes the testing error while meeting their specific needs and constraints.

6 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?