Low-Rank Matrix Approximation¶

-A common problem in many areas of large-scale machine learning involves deriving a useful and efficient approximation of a large matrix.

-This matrix may be the Gram matrix associated to a positive definite kernel in kernel-based algorithms in classification, dimensionality reduction, or some other large matrix arising in other learning tasks such as clustering, collaborative filtering, or matrix completion.

-For these large-scale problems, the number of matrix entries can be in the order of tens of thousands to millions. So we need to find alternative ways to approximate these SVD matricies

import numpy as np

def low_rank_approx(SVD=None, A=None, r=1):
    """
    Computes an r-rank approximation of a matrix
    given the component u, s, and v of it's SVD
    Requires: numpy
    """
    if not SVD:
        SVD = np.linalg.svd(A, full_matrices=False)
    u, s, v = SVD
    Ar = np.zeros((len(u), len(v)))
    for i in range(r):
        Ar += s[i] * np.outer(u.T[i], v[i])
    return Ar

if __name__ == "__main__":
    """
    Test: visualize an r-rank approximation of `ascent`
    for increasing values of r
    Requires: scipy, matplotlib
    """
    from scipy.misc import ascent
    import matplotlib.pyplot as plt
    x = ascent()
    u, s, v = np.linalg.svd(x, full_matrices=False)
    i = 1
    plt.figure()
    plt.ion()
    while i < len(x) - 1:
        y = low_rank_approx((u, s, v), r=i)
        plt.imshow(y, cmap='gray')
        plt.draw()
        i += 1
        #print percentage of singular spectrum used in approximation
        print("{:.2f}".format(100 * i / 512.))

References¶

(https://cs.nyu.edu/~mohri/low_rank.html)

Thank you Tristan Hearn for your wonderful insight

(https://arxiv.org/pdf/1812.07903.pdf)