Почему моя рандомизированная реализация SVD использует так много памяти? - PullRequest
Новая
       7

Почему моя рандомизированная реализация SVD использует так много памяти?

0 голосов
/ 06 ноября 2018

У меня есть реализация Julia (ниже) рандомизированного SVD из этой статьи, Поиск структуры со случайностью: вероятностные алгоритмы для построения приближенных матричных разложений . Если вам интересно, см. Алгоритм на стр. 9.

Я бы ожидал, что рандомизированный SVD будет более эффективным, чем SVD, для больших наборов данных, но он немного медленнее и использует способ больше памяти. Вот моя статистика эффективности от @time: 

 SVD:  16.331761 seconds (17 allocations: 763.184 MiB, 0.82% gc time)
 RSVD: 17.009699 seconds (38 allocations: 1.074 GiB, 0.83% gc time)

Обратите внимание, что мой рандомизированный SVD использует более 1 ГБ памяти. Я не уверен почему. Вот моя реализация: 

using Distributions
using LinearAlgebra

# ------------------------------------------------------------------------------

function find_Q(A, l)
    #=
    Given an m × n matrix A, and an integer l, compute an m × l orthonormal
    matrix Q whose range approximates the range of A.
    =#
    m, n = size(A)
    Ω = rand(Normal(), n, l)
    Y = A * Ω
    Q, R = qr(Y)
    return Q
end

# ------------------------------------------------------------------------------

function randomized_SVD(A, k)
    #=
    Given an m × n matrix A, a target number k of singular vectors, and an
    exponent q (say q = 1 or q = 2), this procedure computes an approximate
    rank-2k factorization UΣVt, where U and V are orthonormal and Σ is
    nonnegative and diagonal.
    =#
    Q = find_Q(A, 2*k)
    B = Q' * A
    S, Σ, Vt = svd(B)
    U = Q * S
    return U, Σ, Vt
end

# ------------------------------------------------------------------------------

m = 2000
n = 20000
k = 10
# Construct low-rank matrix
A = rand(m, k) * rand(k, n)
println("Rank of A: ", rank(A))
println("Size of A: ", size(A))

println("Throwaway test:")
@time svd(A)
@time randomized_SVD(A, k)
println("Actual test:")
@time svd(A)
@time randomized_SVD(A, k)

println("Completed")

Обратите внимание, что я звоню @time дважды по документации Джулии , которая гласит:

При первом вызове (@time sum_global ()) функция компилируется. (Если вы еще не использовали @time в этом сеансе, он также скомпилирует функции, необходимые для определения времени.) Вы не должны серьезно относиться к результатам этого запуска.

1 Ответ

0 голосов
/ 07 ноября 2018

Как дополнительное примечание: в документации Julia не рекомендуется использовать макрос @time для бенчмаркинга. Лучше использовать макрос @benchmark из пакета BenchmarkTools.jl

...