調和矩陣

圖論中,調和矩陣harmonic matrix),也稱拉普拉斯矩陣拉氏矩陣Laplacian matrix)、離散拉普拉斯discrete Laplacian),是矩陣表示。[1]

調和矩陣也是拉普拉斯算子離散化。換句話說,調和矩陣的縮放極限拉普拉斯算子。它在機器學習物理學中有很多應用。

定義

若G是簡單,G有n個頂點,A是鄰接矩陣,D是度數矩陣,則調和矩陣[1]

 

 

動機

這跟拉普拉斯算子有什麼關係?若f 是加權圖G的頂點函數,則[2]

 

w是邊的權重函數。u、v是頂點。f = (f(1), ..., f(n)) 是n維的矢量。上面泛函也稱為Dirichlet泛函。[3]

接續矩陣

而且若K是接續矩陣(incidence matrix),則[2]

 

 

Kf 是f 的圖梯度。另外,特徵值滿足

 

舉例

度矩陣 鄰接矩陣 調和矩陣
       

其他形式

對稱正規化調和矩陣

 

 

注意[4]

 

 

 

例如,離散的冷卻定律使用調和矩陣[5]

 

使用矩陣矢量

 

 

解是

 

 

 

平衡舉動

 的時候,

 

 

 

 

MATLAB代碼

N = 20;%The number of pixels along a dimension of the image
A = zeros(N, N);%The image
Adj = zeros(N*N, N*N);%The adjacency matrix

%Use 8 neighbors, and fill in the adjacency matrix
dx = [-1, 0, 1, -1, 1, -1, 0, 1];
dy = [-1, -1, -1, 0, 0, 1, 1, 1];
for x = 1:N
   for y = 1:N
       index = (x-1)*N + y;
       for ne = 1:length(dx)
           newx = x + dx(ne);
           newy = y + dy(ne);
           if newx > 0 && newx <= N && newy > 0 && newy <= N
               index2 = (newx-1)*N + newy;
               Adj(index, index2) = 1;
           end
       end
   end
end

%%%BELOW IS THE KEY CODE THAT COMPUTES THE SOLUTION TO THE DIFFERENTIAL
%%%EQUATION
Deg = diag(sum(Adj, 2));%Compute the degree matrix
L = Deg - Adj;%Compute the laplacian matrix in terms of the degree and adjacency matrices
[V, D] = eig(L);%Compute the eigenvalues/vectors of the laplacian matrix
D = diag(D);

%Initial condition (place a few large positive values around and
%make everything else zero)
C0 = zeros(N, N);
C0(2:5, 2:5) = 5;
C0(10:15, 10:15) = 10;
C0(2:5, 8:13) = 7;
C0 = C0(:);

C0V = V'*C0;%Transform the initial condition into the coordinate system 
%of the eigenvectors
for t = 0:0.05:5
   %Loop through times and decay each initial component
   Phi = C0V.*exp(-D*t);%Exponential decay for each component
   Phi = V*Phi;%Transform from eigenvector coordinate system to original coordinate system
   Phi = reshape(Phi, N, N);
   %Display the results and write to GIF file
   imagesc(Phi);
   caxis([0, 10]);
   title(sprintf('Diffusion t = %3f', t));
   frame = getframe(1);
   im = frame2im(frame);
   [imind, cm] = rgb2ind(im, 256);
   if t == 0
      imwrite(imind, cm, 'out.gif', 'gif', 'Loopcount', inf, 'DelayTime', 0.1); 
   else
      imwrite(imind, cm, 'out.gif', 'gif', 'WriteMode', 'append', 'DelayTime', 0.1);
   end
end
 
GIF:離散拉普拉斯過程,使用拉普拉斯矩陣

應用

參考文獻

  1. ^ 1.0 1.1 Weisstein, Eric W. (編). Laplacian Matrix. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2020-02-14]. (原始內容存檔於2019-12-23) (英語). 
  2. ^ 2.0 2.1 Muni Sreenivas Pydi (ముని శ్రీనివాస్ పైడి)'s answer to What's the intuition behind a Laplacian matrix? I'm not so much interested in mathematical details or technical applications. I'm trying to grasp what a laplacian matrix actually represents, and what aspects of a graph it makes accessible. - Quora. www.quora.com. [2020-02-14]. 
  3. ^ 3.0 3.1 Shuman, David I.; Narang, Sunil K.; Frossard, Pascal; Ortega, Antonio; Vandergheynst, Pierre. The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains. IEEE Signal Processing Magazine. 2013-05, 30 (3): 83–98 [2020-02-14]. ISSN 1053-5888. doi:10.1109/MSP.2012.2235192. (原始內容存檔於2020-01-11). 
  4. ^ Chung, Fan. Spectral Graph Theory. American Mathematical Society. 1997 [1992] [2020-02-14]. ISBN 978-0821803158. (原始內容存檔於2020-02-14). 
  5. ^ Newman, Mark. Networks: An Introduction. Oxford University Press. 2010. ISBN 978-0199206650. 

閱讀

  • T. Sunada. Chapter 1. Analysis on combinatorial graphs. Discrete geometric analysis. P. Exner, J. P. Keating, P. Kuchment, T. Sunada, A. Teplyaev (編). 'Proceedings of Symposia in Pure Mathematics 77. 2008: 51–86. ISBN 978-0-8218-4471-7. 
  • B. Bollobás, Modern Graph Theory, Springer-Verlag (1998, corrected ed. 2013), ISBN 0-387-98488-7, Chapters II.3 (Vector Spaces and Matrices Associated with Graphs), VIII.2 (The Adjacency Matrix and the Laplacian), IX.2 (Electrical Networks and Random Walks).