2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – LutzL Sep 18 '18 at 6:23
  • $\begingroup$ @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? $\endgroup$ – Dushyant Sahoo Sep 20 '18 at 19:41
  • $\begingroup$ 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? $\endgroup$ – Shogun Sep 28 '18 at 3:08
  • $\begingroup$ Duplicate of decompose-a-matrix-into-diagonal-term-and-low-rank-approximation ? $\endgroup$ – denis Nov 28 '18 at 10:15
1
$\begingroup$

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)

enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.