Page MenuHomec4science
Files F121688064

best_const.html
No OneTemporary
Actions

File Metadata

Created
Sun, Jul 13, 04:26

best_const.html
View Options

<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Computes the constant edge weight that yields fastest averaging.</title>
<link rel="canonical" href="http://cvxr.com/cvx/examples/graph_laplacian/html/best_const.html">
<link rel="stylesheet" href="../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Computes the constant edge weight that yields fastest averaging.</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
Text output
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="keyword">function</span> [w,rho] = best_const(A)
<span class="comment">% [W,RHO] = BEST_CONST(A) gives a vector of the best constant edge weights</span>
<span class="comment">% for a graph described by the incidence matrix A (NxM). N is the number of</span>
<span class="comment">% nodes, and M is the number of edges. Each column of A has exactly one +1</span>
<span class="comment">% and one -1.</span>
<span class="comment">%</span>
<span class="comment">% The best constant edge weight is the inverse of the average of</span>
<span class="comment">% the second smallest and largest eigenvalues of the unweighted Laplacian:</span>
<span class="comment">% W = 2/( lambda_2(A*A') + lambda_n(A*A') )</span>
<span class="comment">% RHO is computed from the weights W as follows:</span>
<span class="comment">% RHO = max(abs(eig( eye(n,n) - (1/n)*ones(n,n) - A*W*A' ))).</span>
<span class="comment">%</span>
<span class="comment">% For more details, see the references:</span>
<span class="comment">% "Fast linear iterations for distributed averaging" by L. Xiao and S. Boyd</span>
<span class="comment">% "Fastest mixing Markov chain on a graph" by S. Boyd, P. Diaconis, and L. Xiao</span>
<span class="comment">% "Convex Optimization of Graph Laplacian Eigenvalues" by S. Boyd</span>
<span class="comment">%</span>
<span class="comment">% Almir Mutapcic 08/29/06</span>
[n,m] = size(A);
<span class="comment">% max degrees of the nodes</span>
Lunw = A*A'; <span class="comment">% unweighted Laplacian matrix</span>
eigvals = sort(eig(Lunw));
<span class="comment">% max degree weigth allocation</span>
alpha = 2/(eigvals(2) + eigvals(n));
w = alpha*ones(m,1);
<span class="comment">% compute the norm</span>
<span class="keyword">if</span> nargout &gt; 1,
rho = norm( eye(n) - A*diag(w)*A' - (1/n)*ones(n) );
<span class="keyword">end</span>
</pre>
</div>
</body>
</html>

Event Timeline

c4science · Help