Compressed svd algorithm implementation

Specific Domains Numerics
,
1

I am trying to implement the compressed SVD in this [https://openaccess.thecvf.com/content_ICCV_2017_workshops/papers/w25/Erichson_Compressed_Singular_Value_ICCV_2017_paper.pdf]. Attached is the algorithm.

I have problems implementing the algorithm as when I apply it to an image, all I get is just black image.
It seems I am missing something any help.

I’d appreciate any help.

Here is the code I implemented in Julia.

function compressed_SVD(X,k,p=10)
    m,n=size(X)
    l=k+p
    Phi=rand(l,m)
    Y=Phi*X
    Btemp=Y*transpose(Y)
    println(size(Btemp))
    B=0.5*(Btemp+transpose(Btemp))
    tempD,tempT=eigen(B)
    D= tempD[1:k]
    T =tempT[:,1:k]
    Shat=diagm(sqrt.(D))
    Vhat=transpose(Y)*T*inv(Shat)
    Uhat=X*Vhat
    U,S,Qt=svd(Uhat)
    V=Vhat*transpose(Qt)
    return U,diagm(S),transpose(V)
end 
![cSVD|690x431](upload://5pd6lcnmUxv9mIzAEBWG4Rhj28S.jpeg)

Below is the algorithm.

(1) l ← k + p Slight oversampling

(2) ← rand(l,m) Generate l Å~ m random test matrix.

(3) Y ← ∗ X Sketch input matrix.

(4) B ← Y ∗ Y⊤ Form smaller l Å~ l matrix.

(5) B ← 1

2 . (B + B⊤) Ensure symmetry.

(6) T,D ← eig(B, k) Truncated eigendecomposition.

(7) ˜S ← √D Rescale eigenvalues.

(8) ˜V ← Y⊤ ∗ T ∗ ˜S−1 Approx. right singular values.

(9) ˜U ← X ∗ ˜V Approx. unscaled left singular vals.

(10) U, S,Q⊤ ← svd(˜U) Update left singular vectors and vals.

(11) V ← ˜VQ

1 Like
2

How to you load and view the image?

Can you provide a minimal working example including the using command, the loading and the viewing of the image?

3

I use the test images package in Julia
the code is

using TestImages
using LinearAlgebra

imag=TestImages.testimage("mandrill")
grayimg=Gray.(imag)
imagmatrix=channelview(grayimg)

This is how I view images

4

Picking the first k eigen values picked the smallest k, which you can fix by sorting them in reverse order. Here’s working code:

import TestImages
import Images
import ImageInTerminal
import LinearAlgebra

function compressed_svd(X::AbstractMatrix, k::Int, p::Int = 10)
    m, n = size(X)
    l = k + p
    Φ = rand(l, m)
    Y = Φ * X
    B = Y * Y'
    B = 0.5 * (B + B')
    D, T = LinearAlgebra.eigen(B; sortby = λ -> -λ)
    D, T = D[1:k], T[:, 1:k]
    S̃⁻¹ = LinearAlgebra.Diagonal(1 ./ sqrt.(D))
    Ṽ = Y' * T * S̃⁻¹
    Ũ = X * Ṽ
    F = LinearAlgebra.svd(Ũ)
    V = Ṽ * F.V
    return F.U, LinearAlgebra.Diagonal(F.S), V
end 

image = TestImages.testimage("mandrill")
gray_image = Images.Gray.(image);
image_matrix = Images.channelview(gray_image);
U, S, V = compressed_svd(image_matrix, 20);
M = Images.clamp01!(U * S * V');
Images.colorview(Images.Gray, M)
1 Like
5

Thank you. I didn’t notice that.

1 Like