sdd: Semidiscrete Decomposition

Description Usage Arguments Details Value Note Author(s) References Examples

Description

The semidiscrete decomposition (SDD) approximates a matrix as a weighted sum of outer products formed by vectors with entries constrained to be in the set {-1, 0, 1}.

Usage

1
sdd(A, kmax = 100, alphamin = 0.01, lmax = 100, rhomin = 10e-20)

Arguments

A

matrix of values on which to run sdd

kmax

number of outer-loop iterations (see References)

alphamin

progress check (see References)

lmax

number of inner-loop iterations (see References)

rhomin

threshold test (See References)

Details

The semidiscrete decomposition (SDD) approximates a matrix as a weighted sum of outer products formed by vectors with entries constrained to be in the set {-1, 0, 1}.

It is useful for image compression and for latent semantic indexing (LSI) in information retrieval.

The primary advantage of the SDD over other types of matrix approximations such as the truncated singular value decomposition (SVD) is that it typically provides a more accurate approximation for far less storage.

The package has been ported from Matlab code given on http://www.cs.umd.edu/~oleary/SDDPACK/. See the webpage for full documentation.

Value

x

matrix of X's, where A is approximately equal to X%*%diag(D)%*%Y

d

vector of D's, where A is approximately equal to X%*%diag(D)%*%Y

y

matrix of Y's, where A is approximately equal to X%*%diag(D)%*%Y

Note

Ported to R by Eric Sun <esun@cs.stanford.edu>

Author(s)

Tamara G. Kolda, Dianne P. O'Leary (Matlab code)

References

http://www.cs.umd.edu/~oleary/SDDPACK/

Examples

1
2
A = matrix(rnorm(100), nrow=10)
sdd(A)

Example output

$x
                                                                               
 [1,]  0  0  0 -1 -1  0  0  0 -1  0  1  1  0 -1  1 0 -1 -1  1  1  0  0 -1  1  1
 [2,]  1  1 -1  0 -1  0  0  1  1 -1  0  1  1  1  0 1  0  0  0  1 -1 -1  0 -1  0
 [3,]  0  0 -1 -1  1  0 -1 -1  1 -1  1  0  0 -1  1 0  1  1 -1 -1 -1  0  0  0  1
 [4,] -1  0 -1  0  0  1  1 -1 -1 -1 -1  1  0 -1 -1 0  1  1  1  0  1  0  0  1  0
 [5,] -1  0  1  0  0  0 -1  0 -1 -1  0 -1  0  0  1 0  0  0 -1 -1  0 -1  0  0 -1
 [6,]  0  1  0 -1  1  0  1  0  0  0  1  1 -1  1  1 0  0  1  0  0  0  1  1  1  0
 [7,] -1 -1 -1  1  0  0 -1  1  0  0  1 -1  1  0  1 0 -1  1  1 -1  0  0  0  1  0
 [8,]  0 -1  0 -1 -1 -1  1  0  0  0  0  0  0 -1 -1 0  0 -1  0 -1  0 -1  1  0 -1
 [9,] -1  1  0 -1  0  0  0  0 -1 -1 -1  1  0 -1  0 0 -1  0 -1  1 -1  1  0  0 -1
[10,] -1  1  0 -1 -1  0 -1 -1  0  1  1  1  1  1  0 0  1  0  1 -1 -1  1  0  1 -1
                                                                             
 [1,]  0  0 -1 -1  1  1  0 -1  0  0  1 -1 -1  0 -1  1  0 -1  1  1  1  1  0  1
 [2,]  1  0 -1  0 -1 -1  0 -1 -1  1  0  1  0 -1  1  1  1  0  0  0  0 -1  1  0
 [3,]  0 -1  0  0  0  1 -1  0  1 -1  1  1  0 -1 -1  0 -1 -1  1 -1  0  1  0  0
 [4,] -1  0 -1  1  1 -1 -1 -1  1 -1 -1  0  0 -1  1  0 -1 -1 -1  1 -1  1  1  0
 [5,]  1  0  0 -1 -1  0 -1  0  0  1  0 -1 -1 -1  0  0 -1  0  1  0  0  0  0  0
 [6,]  1  0 -1  1  0  1  0  1  0 -1  0 -1 -1  1  1 -1 -1 -1  0  0  1  0 -1 -1
 [7,] -1 -1 -1  0  0  0  1 -1 -1 -1  1 -1 -1 -1 -1 -1 -1 -1  1 -1 -1  1  0  0
 [8,] -1  0 -1  0  0  1  0  1  0  0  1  1  0  0  1  0  0 -1  1  0  0  0  1 -1
 [9,] -1  0  0 -1 -1 -1 -1  0 -1 -1 -1  1  0 -1  0  1 -1  1  1  1  0  0  0  0
[10,]  0  1  0  0  0  0  0  0  1  0  1  1 -1  0  1  0  1  1  1 -1  0  1  0 -1
                                                                             
 [1,]  1  0 -1  0  0  1  1  0  0  1 -1  0  0  0  1  1  1 -1 -1  0  1  0 -1 -1
 [2,]  0  0  0 -1  0  1  0  1 -1 -1 -1  0  0  0 -1 -1 -1 -1  0  1  0  0  0 -1
 [3,]  1  1  0  0  0 -1  1  0 -1  1  1  0 -1  0  0  0  0  0 -1  0  0  1  1  0
 [4,] -1  0  0  0 -1  0  0 -1 -1  1  1 -1  1  0  1  1 -1  0  0  1  0  1  0  1
 [5,]  0  0 -1  0  1 -1 -1  0 -1  0  1  1  0  1  1  0  1  0 -1 -1  1  1 -1  0
 [6,]  0  0 -1  0  1  1 -1  0  1  1  0  0 -1 -1 -1  0  1  0  1 -1  1  0  1  1
 [7,]  0 -1 -1  0  1  1  1  1  0 -1  0 -1  0  1 -1  0  1  0  0  0  1 -1 -1  0
 [8,]  1  0  1  1  0  1  0 -1 -1 -1  1  0  0 -1  0  0  0  0  1 -1  1  0 -1  0
 [9,]  1 -1 -1  0 -1  0  1 -1  0  0  0  0  0 -1  1 -1  1  1  0  0  0  0  0 -1
[10,] -1  0  0  1 -1  0  0  1 -1  1  0 -1 -1  1  0  0  0  1 -1 -1 -1 -1  0  1
                                                                               
 [1,]  0  0  0 -1  1 -1  0 -1  0  1  1 -1  0 -1  0 -1  0 -1  1  0 0  0 -1  0  1
 [2,] -1 -1  0  1  1 -1 -1  0  0  0 -1  0 -1 -1  0  1  1  0  1 -1 0  0  1  1  0
 [3,]  1  1  0  1  1  0  1  1  1  1  1  1  1  0  0  0  0  0  1  0 1 -1 -1  0 -1
 [4,]  0  0  1  0 -1 -1  0  0 -1  0  0  0  0  0  1 -1  1  1  0 -1 0  1 -1  1 -1
 [5,]  0 -1 -1  0  0  1 -1  0  1  1 -1 -1  0  1  0  0  1  1  1  1 0  0  1  1 -1
 [6,]  0 -1  0  0  0  0  0  1  1  0  0 -1  0  1  1  1  0  0  1  1 1  1  1 -1  0
 [7,]  1  0  0  1  0  1 -1 -1  0  1 -1  0  0  1 -1 -1  0  1  0  0 1  1  0  0  1
 [8,]  0  1  1  1  1  0 -1  0  0 -1  1  0  0  0  0 -1  1 -1 -1  1 1  0 -1  1  0
 [9,]  1 -1  1  0  0 -1  1 -1  1 -1 -1  0  1 -1  0  0  1  0 -1  1 0  1  0  0  0
[10,]  0  0  0  0  1  0  0 -1  0 -1 -1  0  0 -1  0  0 -1  1  0  0 1  0  0 -1  0
           
 [1,]  0 -1
 [2,] -1 -1
 [3,] -1  0
 [4,]  0  0
 [5,] -1  1
 [6,]  0 -1
 [7,] -1  0
 [8,] -1  0
 [9,] -1  0
[10,] -1  1

$d
  [1] 7.475118e-01 7.175652e-01 8.227342e-01 3.301819e-01 5.613795e-01
  [6] 6.419292e-01 4.073040e-01 2.944641e-01 4.605838e-01 2.278536e-01
 [11] 1.742302e-01 1.805593e-01 2.432678e-01 1.624615e-01 2.178666e-01
 [16] 2.959007e-01 1.822302e-01 1.199071e-01 1.190462e-01 5.876378e-02
 [21] 7.178288e-02 5.247941e-02 7.264214e-02 4.396722e-02 3.721253e-02
 [26] 3.308639e-02 3.627223e-02 2.685901e-02 1.816245e-02 3.363641e-02
 [31] 2.804515e-02 2.603759e-02 1.162986e-02 1.105823e-02 7.883801e-03
 [36] 1.670424e-02 5.164284e-03 6.763550e-03 7.542194e-03 7.037015e-03
 [41] 1.006001e-02 5.784963e-03 5.679659e-03 3.786845e-03 5.465679e-03
 [46] 2.985631e-03 1.965327e-03 4.235258e-03 2.278530e-03 1.476986e-03
 [51] 1.847830e-03 1.755129e-03 1.993064e-03 1.609652e-03 9.784657e-04
 [56] 8.015648e-04 9.801410e-04 7.060937e-04 5.244912e-04 4.570337e-04
 [61] 4.401964e-04 9.070386e-04 3.321407e-04 4.077167e-04 2.672027e-04
 [66] 4.581664e-04 2.774248e-04 1.544031e-04 1.670289e-04 9.834834e-05
 [71] 1.845007e-04 1.553917e-04 7.812729e-05 7.302220e-05 7.205621e-05
 [76] 7.245066e-05 5.248978e-05 7.804247e-05 5.845325e-05 4.868747e-05
 [81] 4.319304e-05 2.814451e-05 2.123464e-05 3.557497e-05 2.426180e-05
 [86] 3.817365e-05 1.220277e-05 2.039952e-05 1.174712e-05 8.466911e-06
 [91] 7.469365e-06 8.110438e-06 5.671511e-06 6.136449e-06 5.216119e-06
 [96] 4.389743e-06 9.564996e-06 2.955949e-06 2.377918e-06 2.179884e-06

$y
                                                                             
 [1,]  1  0 -1  1 -1  0  0  1 0 -1 -1  0  1 1 0  0 0 -1 0 0  0  0 -1  0  0 -1
 [2,] -1  1  0  0  0  1  1  1 0  0  0  0 -1 0 0  0 0 -1 0 1  0  0  0  0  1  1
 [3,]  1  1  0 -1  0  0 -1 -1 1 -1  1  0  0 0 0  0 0  0 0 1  1  1  0 -1  1 -1
 [4,]  0 -1  1 -1  0  0  1  0 0  0 -1 -1  0 0 0 -1 0  1 0 1 -1  1  0  0 -1  0
 [5,]  1  1  1  1  0  1 -1  1 0  1  0  0 -1 1 0  0 0  0 0 0 -1  1  1  0 -1  0
 [6,] -1  1  0  1  1  0  1  0 0  0  1  0  0 0 1  0 0  0 0 1  0  0  1  1  0  0
 [7,]  1  0  0  0  1  0  0  1 0 -1  1  1  0 0 0  1 0  1 0 1  0 -1  1 -1  0 -1
 [8,]  0 -1  1 -1 -1  1  0  1 0 -1  1 -1  0 0 0  0 1  0 0 0 -1  0  0  1  1  0
 [9,]  1  0  0  1  0  1  0 -1 0 -1 -1  1  0 0 0  1 0  1 0 0  1  1  0  0  1  1
[10,]  1  0  0 -1  0 -1  1  1 0 -1  0 -1 -1 0 0  0 0  0 1 0  0  0  0  0  0  0
                                                                              
 [1,]  0  0  0 0 0  1  1 0  0 0 -1  1  0 -1 0 0 0 -1 0 -1 -1  0  0  0  1 0 0 0
 [2,]  1  0  0 0 0  0  0 1  1 0  1  1  0  0 0 0 0  0 1  0  0  0 -1  0 -1 0 0 0
 [3,]  0  0  0 0 0 -1  1 0  0 0  0  1  1  0 0 0 0  0 0  1  0  0 -1  0  1 1 0 0
 [4,]  0  1 -1 0 0  0  1 0  0 0 -1 -1  0  0 0 0 0 -1 1  1  1  0  0  1  0 0 1 0
 [5,]  0  0  1 0 0  0  0 1  0 0 -1  0  0  1 0 0 0 -1 0 -1  1  1  0  0  0 0 0 1
 [6,]  0 -1 -1 1 0  0  0 0  1 0 -1  0  0  0 1 0 0  0 0  1  1  0  1 -1  1 0 0 0
 [7,]  1  0  0 0 0  0 -1 0  0 1  1  0  0  0 0 0 0  0 0 -1  1 -1  0 -1  0 0 0 0
 [8,] -1  0 -1 0 0  0  1 1 -1 0  1  0 -1  0 0 1 0  0 0  0  0  0  0  0  1 0 0 0
 [9,]  0 -1  0 0 1  0  0 0  0 0 -1 -1  0  0 0 0 1  0 0 -1  0  0 -1  1  0 0 0 0
[10,]  0  1  1 0 0  0 -1 1 -1 0 -1  1  0  0 0 0 0  1 0  0  0  0  1  1  1 0 0 0
                                                                               
 [1,]  0  1 1 0  1 -1 -1 0 1 0 -1 0  0  0 -1 -1 1 0  0 -1 0  0  0  0 1  0  0  1
 [2,]  0  0 0 1  0  0  0 1 0 0  1 0  0  1  0 -1 0 1  0  1 0 -1  1  0 0  0  0 -1
 [3,]  0  0 1 0  0  1  1 0 0 0  1 0  0  1  1  1 0 0  1 -1 0  0  1 -1 0 -1  0  0
 [4,]  0  0 0 0  0  0 -1 0 1 0  0 0  0 -1  1 -1 0 0  0 -1 1  1 -1  0 0  0  0  0
 [5,]  0  0 0 0  0  0  1 0 0 1  0 0 -1  0  0  0 0 0  1  1 0  0  0  0 0  1 -1  1
 [6,]  1 -1 0 1  1 -1  0 0 0 0  1 0  0 -1  0  1 0 0  1  0 1  0  0  0 0  0  1  0
 [7,] -1  1 0 1 -1  0  0 0 1 0  0 1  0  0  0  0 0 0  1  1 1  1 -1  0 0 -1 -1 -1
 [8,]  1  1 0 0  0  1 -1 0 0 0  1 0 -1  0 -1  0 0 0 -1  0 0  1  1  0 0 -1  0  1
 [9,] -1  0 0 1  0  1  0 0 0 0  1 0  1  0 -1 -1 0 0  1 -1 0  0  1  1 0  0  0  0
[10,]  1  1 0 0  0  0  1 0 1 0  0 0 -1  1  0  1 0 0 -1  1 1 -1  0  0 1  0  0 -1
                                                      
 [1,] -1 0  0 0  1 1 -1  1  0 -1  1  0  1 0 0 -1  1 -1
 [2,]  0 1  0 0 -1 0  0  0  0  0  1 -1  0 0 0  0  0  1
 [3,]  0 0  1 0  0 1 -1 -1  1  0 -1  1  1 0 0 -1  0  0
 [4,]  1 0  0 0  0 0  0  1  1  1  0  0  0 0 1  0  0 -1
 [5,]  1 0  1 1 -1 0 -1  1  1  0  1  0 -1 1 0  1  1  0
 [6,]  1 0  0 0  0 1 -1  0 -1  0 -1  0 -1 0 0 -1  1  0
 [7,]  0 0  0 0  1 1  0 -1  0  0  1  1  0 1 0 -1 -1  0
 [8,]  0 0  1 0 -1 1  1  1 -1  1  0  1  0 0 0  0  1  1
 [9,]  1 0 -1 0 -1 1 -1 -1 -1  0  0 -1  1 0 0  1 -1 -1
[10,]  1 0  0 0  0 0  1  0  1  0 -1 -1  0 1 0 -1  1 -1

sddpack documentation built on May 2, 2019, 4:14 a.m.