1
vote
0answers
57 views

Recovering Spherical Harmonics from Discrete Samples

Consider a collection of $N$ points on the 2-sphere chosen uniformly at random. Let's say that there's an edge between two such vertices if their geodesic distance is less than $r_N$. The resulting ...
1
vote
1answer
72 views

Neighborhood overlap matrix for a bipartite graph

Let $G$ be an undirected, simple, bipartite graph with parts $V$ (having $n$ vertices) and $W$ (having $m$ vertices). Define the following $n$-by-$n$ matrix: for any $i,j \in V$, $$a_{ij} = |N_i \cap ...
1
vote
0answers
49 views

interpretation of generalized eigenvalue/vectors in spectral graph theory

Let us say I have a symmetric graph adjacency matrix A, a degree matrix D, a laplacian L (D-A). I have a generalized eigenvalue equation $Av=\lambda Lv$. Does the eigenvalue/vectors produced in this ...
2
votes
1answer
155 views

positive semidefinite matrix condition

There is a great work of Alizadeh that in section 4 speaks about Minimizing sum of the first few(k-largest) eigenvalues of a symmetric matrix. Instead of a symmetric model we use the weighted ...
1
vote
0answers
63 views

Second eigenvalue of a weighted tree

Hello, I am interested in upper bounding the second largest eigenvalue of the adjacency matrix of a graph $T$ with the following property: 1. $T$ contains self loops. 2. $T$ contains multiple edges ...
1
vote
0answers
115 views

Recovering a partition from spectral properties of the graph Laplacian

Let $G$ be a weighted graph with vertices $V$. Let $W$ be its real-valued, non-negative, $|V|\times|V|$ adjacency/affinity matrix. Let $L = \mathrm{diag}(W\mathbf1)-W$ be the (unnormalized) graph ...
1
vote
0answers
105 views

Optimization over Spectral Laplacian in cycles and trees

Is there any idea on how one can deal with an optimization problem of sum of k largest eigenvalues(min) of Laplacian matrix of a simple cycle or tree? I would like to use semidefinite programming for ...
3
votes
1answer
199 views

What is the spectrum of the Rado graph?

Isn't this question self-explanatory? There is a lot of literature about the Rado graph $R$ in various places. This graph is also known as the "Random Graph" because a countable random graph is ...
7
votes
1answer
348 views

Is the Cheeger constant of an induced subgraph of a cube at most 1?

It is known that the Cheeger constant of a hypercube graph $Q_n$ is exactly $1$, regardless of its dimension $n$. Is $1$ also an upper bound on the Cheeger constant of nontrivial induced connected ...
3
votes
4answers
905 views

Boundaries of the eigenvalues of a symmetric matrix (or of its Lapacian)

Given the adjacency matrix $A_{ij}$ of a graph with $N$ vertices and $M$ links (or any binary symmetric matrix of size $N \times N$), is it possible to establish lower and upper boundaries of its ...
2
votes
1answer
211 views

Singular values of differences of square matrices

Suppose $A, B \in \mathbb{R}^{n \times n}$. Let $\sigma_1(A),\ldots,\sigma_n(A)$ be the singular values of $A$, and let $\sigma_1(B),\ldots,\sigma_n(B)$ be the singular values of $B$. If I know these ...
5
votes
1answer
301 views

What is the Cheeger constant of a cubical subset of the cubic lattice?

The Cheeger constant of a finite graph measures the "bottleneckedness" of the graph, and is defined as: $$h(G) := \min\Bigg\lbrace\frac{|\partial A|}{|A|} \Bigg| A\subset V, 0<|A|\leq ...
11
votes
2answers
937 views

Combinatorial proof of (a special case of) the spectral theorem?

The spectral theorem for a real $n \times n$ symmetric matrix $A$ says that $A$ is diagonalizable with all eigenvalues real. If $A$ happens to have non-negative integer entries, it can be interpreted ...
14
votes
1answer
2k views

Fast Fourier Transform for Graph Laplacian?

In the case of a regularly-sampled scalar-valued signal $f$ on the real line, we can construct a discrete linear operator $A$ such that $A(f)$ approximates $\partial^2 f / \partial x^2$. One way to ...