Обобщенная обратная Мура-Пенроуза большой разреженной матрицы

У меня есть квадратная матрица с несколькими десятками тысяч строк и столбцов с несколькими 1 рядом с тоннами 0, поэтому я использую пакет Matrix для эффективного хранения этого в R. Объект base::matrix не может обработать такое количество ячеек, так как мне не хватает памяти.

Моя проблема в том, что мне нужна обратная, а также обобщенная обратная Мура-Пенроуза таких матриц, которые я не могу вычислить в настоящее время.

Что я пробовал:

  • solve выдает ошибку Error in LU.dgC(a) : cs_lu(A) failed: near-singular A (or out of memory)
  • MASS::ginv несовместим с классом Matrix
  • нет прямого способа преобразовать разреженный Matrix, например. bigmemory::big.matrix, а последний все равно не работает с MASS::ginv
  • если я попытаюсь вычислить факторизацию Холески матрицы, чтобы позже вызвать для этого Matrix::chol2inv, я получу следующее сообщение об ошибке:

    Error in .local(x, ...) : 
      internal_chm_factor: Cholesky factorization failed
    In addition: Warning message:
    In .local(x, ...) :
      Cholmod warning 'not positive definite' at file ../Cholesky/t_cholmod_rowfac.c, line 431
    
  • основываясь на связанном вопросе, я также попробовал pbdDMAT пакет на одном узле, но pbdDMAT::chol выдал сообщение об ошибке Cholmod error 'out of memory' at file ../Core/cholmod_memory.c, line 147

Вопрос в двух словах: есть ли способ вычислить обратную и обобщенную обратную Мура-Пенроуза такой разреженной матрицы, помимо использования класса matrix на компьютере с тоннами оперативной памяти?


Краткий воспроизводимый пример:

library(Matrix)
n <- 1e5
m <- sparseMatrix(1:n, 1:n, x = 1)
m <- do.call(rBind, lapply(1:10, function(i) {
    set.seed(i)
    m[-sample(1:n, n/3), ]
}))
m <- t(m) %*% m

Некоторые описания (спасибо Габору Гротендику):

> dim(m)
[1] 100000 100000
> sum(m) / prod(dim(m))
[1] 6.6667e-05
> table(rowSums(m))

    0     1     2     3     4     5     6     7     8     9    10 
    5    28   320  1622  5721 13563 22779 26011 19574  8676  1701 
> table(colSums(m))

    0     1     2     3     4     5     6     7     8     9    10 
    5    28   320  1622  5721 13563 22779 26011 19574  8676  1701 

И некоторые сообщения об ошибках:

> Matrix::solve(m)
Error in LU.dgC(a) : cs_lu(A) failed: near-singular A (or out of memory)
> base::solve(m)
Error in asMethod(object) : 
  Cholmod error 'problem too large' at file ../Core/cholmod_dense.c, line 105
> MASS::ginv(m)
Error in MASS::ginv(m) : 'X' must be a numeric or complex matrix

Целью bounty является поиск способа вычисления обобщенной обратной функции Мура-Пенроуза m с объемом оперативной памяти менее 8 ГБ (скорость и производительность не важны).


person daroczig    schedule 23.05.2014    source источник
comment
Что вам нужно сделать с обратным после того, как вы его вычислите? mathoverflow.net/questions/72616/   -  person Ben Bolker    schedule 25.05.2014
comment
Спасибо, @BenBolker, я пытаюсь реализовать формулу (22) на странице 14 по адресу scribd.com. /doc/226039409#page=14 с большими матрицами. Я также был бы признателен за любую помощь в том, как я мог бы сохранить это вычисление, поскольку вычисление D_1 и D^a_2 было очень быстрым с Matrix::sparseMatrix, но я застрял с обратным (pseduo).   -  person daroczig    schedule 25.05.2014
comment
Скрибд говорит, что это частный документ...   -  person Ben Bolker    schedule 25.05.2014
comment
@BenBolker Я ужасно извиняюсь за эту хромую проблему, попробуйте еще раз, я только что обновил настройки конфиденциальности.   -  person daroczig    schedule 26.05.2014
comment
По какой-то причине ваш пример m не создает квадратные матрицы.   -  person James    schedule 26.05.2014
comment
Спасибо @James, я только что исправил пример. Проблема заключалась в том, что количество строк/столбцов по умолчанию равно max сгенерированного образца.   -  person daroczig    schedule 26.05.2014
comment
Пример также нельзя воспроизвести, если не добавлено set.seed.   -  person G. Grothendieck    schedule 26.05.2014


Ответы (1)


Если у вас очень мало 1, то ваша матрица, скорее всего, будет иметь не более одной 1 в любом столбце и в любой строке, и в этом случае обобщенная инверсия равна транспонированию:

library(Matrix)
set.seed(123)
n <- 1e5
m <- sparseMatrix(sample(1:n, n/10), sample(1:n, n/10), x = 1, dims = c(n, n))

##############################################################################
# confirm that m has no more than one 1 in each row and column
##############################################################################
table(rowSums(m))  # here 90,000 rows are all zero, 10,000 have a single one
##     0     1 
## 90000 10000 

table(colSums(m))  # here 90,000 cols are all zero, 10,000 have a single one
##     0     1 
## 90000 10000 

##############################################################################
# calculate generalized inverse
##############################################################################
minv <- t(m)

##############################################################################
# check that when multiplied by minv it gives a diagonal matrix of 0's and 1's
##############################################################################
mm <- m %*% minv

table(diag(mm)) # diagonal has 90,000 zeros and 10,000 ones
##     0     1 
## 90000 10000 

diag(mm) <- 0
range(mm) # off diagonals are all zero
## [1] 0 0

ИСПРАВЛЕНО Улучшено представление.

person G. Grothendieck    schedule 26.05.2014
comment
Круто, большое спасибо @G-Grothendieck! К сожалению, m имеет несколько 1 в некоторых столбцах/строках, несмотря на то, что он действительно разреженный: sum(m) / prod(dim(m)) возвращает 0.0007337982 в моей матрице. Я пытаюсь придумать лучший пример. - person daroczig; 26.05.2014
comment
Что такое table(rowSums(m)) и table(colSums(m)) и dim(m)? - person G. Grothendieck; 26.05.2014
comment
@G-Grothendieck, пожалуйста, найдите подробности по адресу gist.github.com/daroczig/9bc956ce8e1cb210234a, пока я придумать реальный минимальный воспроизводимый пример. - person daroczig; 27.05.2014
comment
Это кажется более плотным, чем я думал, но вы можете уменьшить размер задачи следующим образом: ix ‹- union(what(rowSums(m) › 0), which(colSums(m) › 0)); минв ‹- м; minv[ix, ix] ‹- f(m[ix, ix])`, где f — обобщенная обратная функция. Кажется, ginv не сработает, но если вы сможете найти другой, возможно, это уменьшит его достаточно, чтобы помочь. - person G. Grothendieck; 27.05.2014
comment
Круто, большое спасибо, @G-Grothendieck! Я оставлю награду открытой еще на несколько дней, но я уверен, что предложенные очки репутации попадут на ваш счет. Спасибо еще раз! - person daroczig; 27.05.2014