Rank comparison for different low rank approximations

I want to approximate a correlation matrix by low-rank components such that $$\Sigma \approx \sum_{i=1}^{k_1} \sigma_ib_ib_i^T$$

where $$\Sigma$$ is of size $$n \times n$$, $$b$$ is a $$n$$ dimensional vector and $$k$$ is the number of components. I was wondering if subtracting a diagonal matrix $$D \in R^{n\times n}$$ from the matrix would give a better low rank approximation, below is the decomposition

$$\Sigma \approx D + \sum_{i=1}^{k_2} \sigma_{i}^{'} b_{i}^{'}b_i^{'T}$$

Can we estimate $$D, \sigma, b$$ such that $$k_2 \leq k_1$$ holds true? Both the above approximations have different $$\sigma$$ and $$b$$.

Also, I know that the $$\Sigma$$ matrix has non-zero diagonal entries and the matrix after removing the diagonal term is sparse.

Edit 1: I was thinking of simulating correlation matrix and then test the above hypothesis. Is there is a way to simulate a low rank, sparse and full diagonal matrix? I have asked this question here https://stats.stackexchange.com/questions/368868/simulation-of-low-rank-and-sparse-matrix

• You can dramatically increase the rank by removing the diagonal. Consider the matrix of all 1 which has rank 1 and has rank n-1 with the diagonal removed. – LutzL Sep 18 '18 at 6:23
• @LutzL Just edited the question, I would like to estimate $D$ such that $k_2 \leq k_1$ should hold true. Is this possible theoretically? – Dushyant Sahoo Sep 20 '18 at 19:41
• your constraint on it being a diagonal matrix but also sparse doesn't make sense. diagonal matrices are sparse. Like the other person said the diagonal matrix will increase the rank of the matrix. I feel like you got this problem from somewhere. Where did it come from? – Shogun Sep 28 '18 at 3:08
• – denis Nov 28 '18 at 10:15

The Eckart Young Mirsky Theorem States the following. Suppose $$A \in \mathbb{R}^{m \times n}$$

$$A = U \Sigma V^{T} \tag{1}$$

then if we take a rank k approximation of the matrix using the SVD

$$A_{k} = \sum_{i=1}^{k} \sigma_{i}u_{i}v_{i}^{t} \tag{2}$$

the difference between them is given as

$$\| A - A_{k} \|_{2} = \bigg\| \sum_{i=k+1}^{n} \sigma_{i}u_{i} v_{i}^{t} \bigg\| = \sigma_{k+1} \tag{3}$$

The best rank k approximation is when the matrix has the given rank k. This is from this expression. If $$A= A_{k}$$ our minimization expression will be minimized.

I am not sure how $$D$$ is going to help you better approximate the matrix $$\Sigma$$. I am sorry about the confusion with notation.

Right, if $$k_{2}$$ is less than $$k$$ it is actually not good

$$\| A + D\| \leq \| A \| + \|D\| \tag{4}$$

and we can approximate both of these. The norm is

$$\| A\|_{2} = \sqrt{\lambda_{max}(A^{*}A)} = \sigma_{max}(A) = \sigma_{1} \tag{5}$$

the 2-norm is the maximum singular value. $$\| A + D\| \leq \sigma_{max}(A) + \sigma_{max}(D) \tag{6}$$

So from above, you have

$$\| A -\Sigma_{1} \|_{2} = \sigma_{k_{1}+1} \tag{7}$$ $$\| A- \Sigma_{2} \|_{2} - \|D \|_{2} \leq \| A - \Sigma_{2} -D \|_{2}\tag{8}$$ Then

$$\| A- \Sigma_{2}\|_{2} = \sigma_{k_{2}+1} \\ \|D\|_{2} = \sigma_{max}(D) \tag{9}$$

$$\sigma_{k_{1}+1} - \sigma_{k_{2}+1} - \sigma_{max}(D) \leq \|A-\Sigma_{1} \|_{2} -\|A-\Sigma_{2} -D\|_{2} \tag{10}$$

Note that singular values are ordered so $$\sigma_{k_{1}+1} \geq \sigma_{k_{2}+1}$$ if $$k_{1} \geq k_{2}$$

Numerical Simulation

I think you wanted a numerical simulation to support your argument so I am going to create the Python code to show you why. I already answered a similar question about SVDs earlier. So I will use that code to show you.

Say we have our covariance matrix or really any matrix $$A$$ and it has a rank $$\alpha$$,

import numpy as np
import matplotlib.pyplot as plt
import math

def gen_rank_k(m,n,k):
# Generates a rank k matrix
# Input m: dimension of matrix
# Input n: dimension of matrix
# Input k: rank of matrix

vec1 = np.random.rand(m,k)
vec2 = np.random.rand(k,n)
rank_k_matrix = np.dot(vec1,vec2)

return rank_k_matrix

m=10
n=m
alpha = 7

A = gen_rank_k(m,n,k)


Now we have $$k_{2} \leq k_{1} \leq \alpha$$

u, s, vh = np.linalg.svd(A, full_matrices = False)

x = np.linspace(1,10,10)

plt.plot(x,s) This is a plot of the singular values of $$A$$

now for the two low rank approximations of $$A$$ choose $$k_{1} = 5, k_{2} = 3$$

def low_rank_k(u,s,vh,num):
# rank k approx

u = u[:,:num]
vh = vh[:num,:]
s = s[:num]
s = np.diag(s)
my_low_rank = np.dot(np.dot(u,s),vh)
return my_low_rank

my_rank_k1 = low_rank_k(u,s,vh,k1)
my_rank_k2 = low_rank_k(u,s,vh,k2)

my_diagonal_matrix  = np.diag(np.random.rand(10))

error1 = np.linalg.norm(A - my_rank_k1)
error2 = np.linalg.norm(A- my_rank_k2 - my_diagonal_matrix)

• I didn't exactly understand the interpretation of your analysis. Shouldn't you analyze $||A-\Sigma_1||_2 - ||A-\Sigma_2-D||_2$? – Dushyant Sahoo Sep 17 '18 at 0:26
• that's probably a better idea. i'll rewrite this – Shogun Sep 17 '18 at 13:35
• I think that's what you're looking for. – Shogun Sep 17 '18 at 18:07
• I wanted to know if I can have $k_2 \leq k_1$ inequality not what will happen if the inequality holds true. – Dushyant Sahoo Sep 20 '18 at 19:58
• I don't think Im saying the inequality is holding true. Also, I've done enough work. – Shogun Sep 20 '18 at 20:44