Tagged Questions

63 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 ...
99 views

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 ... 0answers 64 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 ... 1answer 172 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 ... 0answers 65 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 ... 0answers 120 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 ... 0answers 110 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 ... 1answer 98 views Spectrum of composition of graphs( lexicographic product) I was wondering how to relate the spectra of the composition of two graphs in term of the factors...someone can help me? 0answers 88 views Global solution for spectral clustering I used spectral clustering for directed graphs suggested by Dengyong Zhou paper to partition the graph.I selected the eigen vectors corresponding to k largest eigen values and then I use kmeans or FCM ... 1answer 203 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 ... 1answer 358 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 ... 4answers 942 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 ... 1answer 221 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 ... 1answer 310 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 ...
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 ...
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 ...