Approximate Embedding

Approximate embedding

Given a symmetric affinity matrix $A$, we would like to compute the $k$ smallest eigenvectors of the Laplacian of A. Directly computing such eigenvectors can be very costly even with sophisticated solvers, due to the large size of $A$.

Examples

Approximate embedding examples

Bibliography

Bibliography
+017
Jordi Pont-Tuset, Pablo Arbelaez, Jonathan T Barron, Ferran Marques, and Jitendra Malik. Multiscale combinatorial grouping for image segmentation and object proposal generation. IEEE transactions on pattern analysis and machine intelligence, 2017.

Reference

Index

Content

SpectralClustering.DNCuts — Type.
type DNCuts

Multiscale Combinatorial Grouping for Image Segmentation and Object Proposal Generation

Jordi Pont-Tuset, Pablo Arbeláez, Jonathan T. Barron, Member, Ferran Marques, Jitendra Malik

source
SpectralClustering.LandmarkBasedRepresentation — Type.

Large Scale Spectral Clustering with Landmark-Based Representation Xinl ei Chen Deng Cai

Members

  • landmark_selector::{T <: AbstractLandmarkSelection} Method for extracting landmarks
  • number_of_landmarks::Integer Number of landmarks to obtain
  • n_neighbors::Integer Number of nearest neighbors
  • nev::Integer Number of eigenvectors
  • w::Function Number of clusters to obtain
  • normalize::Bool
source
SpectralClustering.NystromMethod — Type.

type NystromMethod{T<:AbstractLandmarkSelection}
landmarks_selector::T
number_of_landmarks::Integer
w::Function
nvec::Integer
end

The type NystromMethod proposed in Spectral Grouping Using the Nystrom Method by Charless Fowlkes, Serge Belongie, Fan Chung, and Jitendra Malik. It has to be defined:

  • landmarks_selector::T<:AbstractLandmarkSelection. A mechanism to select the sampled

points.

  • number_of_landmarks::Integer. The number of points to sample
  • w::Function. The weight function for compute the similiarity. The signature of the weight function has to be weight(i, j, e1,e2). Where e1 and e2 ara the data elements i-th and j-th respectivily, obtained via get_element, usually is a vector.
  • nvec::Integer. The number of eigenvector to obtain.
  • threaded::Bool. Default: True. Specifies whether the threaded version is used.
source
SpectralClustering.embedding — Method.
embedding(d::DNCuts, L)
source
SpectralClustering.embedding — Method.
embedding(cfg::LandmarkBasedRepresentation, X)
source
SpectralClustering.embedding — Method.

embedding(cfg::NystromMethod, X)

This is an overloaded function

source
SpectralClustering.embedding — Method.

embedding(cfg::NystromMethod, landmarks::Vector{Int}, X)

Arguments

  • cfg::[NystromMethod](@ref)
  • landmarks::Vector{Int}
  • x::Any

Return values

  • (E, L): The approximated eigenvectors, the aprooximated eigenvalues

Performs the eigenvector embedding according to

source
SpectralClustering.embedding — Method.

embedding(cfg::NystromMethod, A::Matrix, B::Matrix, landmarks::Vector{Int})

Performs the eigenvector approximation given the two submatrices A and B.

source
SpectralClustering.create_A_B — Method.

createAB(cfg::NystromMethod, X)

Arguments:

  • cfg::NystromMethod
  • X

#Return values

  • Sub-matrix A
  • Sub-matrix B
  • Vector{Int}. The sampled points used build the sub-matrices

This is an overloaded method. Computes the submatrix A and B according to create_A_B(::NystromMethod, ::Vector{Int}, ::Any). Returns the two submatrices and the sampled points used to calcluate it

source
SpectralClustering.create_A_B — Method.

createAB(cfg::NystromMethod, landmarks::Vector{Int},X)

Arguments:

  • cfg::NystromMethod. The method configuration.
  • landmarks::Vector{T}. A vector of integer that containts the $n$ indexes sampled from the data.
  • X is the data that containt $ N $ patterns.

Let $ W \in \mathbb{R}^{N \times N}, W = \begin{bmatrix} A & B^T \ B & C \end{bmatrix}, A \in \mathbb{R}^{ n \times n }, B \in \mathbb{R}^{(N-n) \times n}, C \in \mathbb{R}^{(N-n)\times (N-n)} $ . $A$ represents the subblock of weights among the random samples, $B$ contains the weights from the random samples to the rest of the pixels, and $C$ contains the weights between all of the remaining pixels. The function computes $A$ and $B$ from the data X using the weight function defined in cfg.

source