# Compressed svd algorithm implementation

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
``````

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

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?

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

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

Thank you. I didn’t notice that.

1 Like