如何從奇異矩陣中均勻採樣

我想從n個Bernoulli矩陣（即每個入口爲1或0，概率爲1/2）對所有奇異n進行均勻採樣。我當然可以從n個Bernoulli矩陣中抽樣，並拒絕那些非奇異的，但對於任何效率極低的中等n。如何從奇異矩陣中均勻採樣

作爲一個例子，在我測試的10000個隨機100乘100矩陣中，沒有一個是單數。

有沒有一種有效的方法來做到這一點？

這裏是一些測試python代碼來顯示問題。

import numpy as np 
iters = 10000 
n = 100 
count = 0 
for i in xrange(iters): 
    A = np.random.randint(2, size = (n,n)) 
    if (np.linalg.matrix_rank(A) < n): 
     count += 1 
print count

發佈到https://mathoverflow.net/questions/155185/how-to-sample-uniformly-from-singular-matrices於1月20日

https://mathoverflow.net/questions/155185/how-to-sample-uniformly-from-singular-matrices現在有一個建議的算法來解決這個問題。剩下的挑戰是如何實施它。

來源

2014-01-17 marshall

您可以嘗試的一個想法是生成第一個n-1行，然後生成最後一行作爲前一個n-1的線性組合。這將保證一個單一的矩陣，但我不知道你會如何去統一。 –

是的，我剛剛意識到。無論如何，也許這對後代有用的參考http://arxiv.org/pdf/1112.0753.pdf :) –

這個問題似乎是題外話題，因爲從編程到計算機科學到研究水平數學，這個問題是在數學的最後。 – mbeckish

的意見漸行漸遠了一點，所以我張貼這作爲一個答案：

這裏有一個紙：http://www.researchgate.net/publication/2729950_Efficient_Generation_of_Random_Nonsingular_Matrices/file/e0b4951d5a6fcc7e67.pdf描述如何生成非奇異，並且，作爲擴展，在奇異矩陣有限域。由於在編程中實數在某種程度上是有限的，所以我認爲它應該適用於此。

來源

2014-01-17 17:41:50

對GF（2）的依賴不一定是對Q的依賴。（儘管如此，整潔的論文。） – tmyklebu

+1。我認爲，如果OP從一篇特定的論文中提出算法，並要求實施方面的幫助，那將是一個很好的問題。要求社區在互聯網上搜索論文，而不是那麼多。 – mbeckish

我還沒有閱讀和理解論文，但是我在第7頁看到了用於生成奇異矩陣的僞代碼。論文中不清楚嗎？ –

如何從奇異矩陣中均勻採樣

回答

相關問題