# Tagged Questions

**1**

vote

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**4**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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 ...