Re: generating a sparse matrix with a specific singular value distribution

On Apr 26, 3:22 pm, Robert Israel
<isr...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
Robert Israel <isr...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx> writes:

Hello,

 I want to test an iterative algorithm on sparse matrices with
different singular value distributions. I can generate a full matrix
with a given singular value distribution by using a reverse SVD
decomposition. That is I know:

A = U*D*V' for any A, where U and V are orthogonal. I can get U and V
from a QR decomposition and supply a D with the singular values that I
want to generate A.

However, is it possible to generate a sparse matrix A in this way
(apart from generating A as above and removing elements at random)?

I would appreciate any ideas on this, thanks for your help.

Use whatever D you want, and very sparse orthogonal matrices U and V.

For example, start with a permutation matrix and multiply a few times by
matrices for 2 x 2 rotations (i.e. randomly choose indices i and j and
an angle theta, and take the matrix M with M_{ii} = M_{jj} = cos(theta),
M_{ij} = -M_{ji} = sin(theta), otherwise as in the identity matrix).
--
Robert Israel              isr...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics        http://www.math.ubc.ca/~israel
University of British Columbia            Vancouver, BC, Canada

Thanks for your suggestions. What I am currently doing to generate an
mxn full matrix A (m<n) is taking:

U mxm orthogonal (from a qr decomposition of a random matrix)
D mxm diagonal with the desired singular values
V nxm orthogonal (from a qr decomposition from another random matrix)

then A = U*D*V'

From your suggestion I would do the same process as above except take
U and V to be very sparse (makes sense - the hard part is generationg
sparse U and V :). I am sligthly confused about your explanation to
generate U and V. Do you mean:

Take some permutation matrix P and multiply this by a rotation matrix?
Suppose I take
an mxm permutation matrix. Then I take an mxm identity matrix M, take
two randomly chosen
indices i and j and set M_{ii} = M_{jj} = cos(theta) and M_{ij} = -M_
{ji} = sin(theta)?

then I compute U = P*M1*M2*M3.. where M's are chosen as above? and the
same for V?

Thanks again for your help.


.

Relevant Pages

  • generating a sparse matrix with a specific singular value distribution
    ... I want to test an iterative algorithm on sparse matrices with ... different singular value distributions. ... with a given singular value distribution by using a reverse SVD ... from a QR decomposition and supply a D with the singular values that I ...
    (sci.math)
  • Re: Eigenvalues and transformations
    ... Is there any connection between the eigenvalues/eigenvectors of X and A? ... I read about the singular value decomposition, and since P is real and A is real too, it can be decomposed into three matrices, the same can be done on Q and I can say this, if I'm not mistaken: ... V is such that V^T V = V V^T = I, the same is for U (if I understand, since they are real matrices). ... In the last line, the matrix S ``preserves'' positive definiteness since singular values are non-negative, but U is just unitary... ...
    (sci.math)
  • Eigen vector calculation
    ... I have one problem regarding Eigen vector calculation. ... Let say X- Data Matrix having dimension m * n ... Now, I want to apply Generalized Singular Value Decomposition, can you ...
    (sci.math)
  • Re: When Does Pseudo-Inverse Exist?
    ... I cant compute it for my sparse square matrix A as det= 0. ... I'm guessing that you're trying to use the formula ^*A' ... You can try using the singular value decomposition. ...
    (sci.math)
  • Re: Probability Distribution
    ... William Elliot wrote: ... x1 = -1 with probability p ... The distributions are singular, and ...
    (sci.math.research)
Loading