ON SIGNAL PROCESSING ON GRAPHS
ON SIGNAL PROCESSING ON GRAPHS
复制标题
关于图上的信号处理
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Begué
中科院分区：
文献类型：
--
作者：
M. Begué
Graph theory has developed into a useful tool in applied mathematics as many modern data sets are or can be represented as a graph. In these data sets, vertices correspond to different sensors, observations, or data points and edges represent connections, similarities, or correlations among those points. Some immediate applied examples include social network data, electricity networks, and images. In fact, in many dimension reduction methods the first step is to create a graph out of the data by identifying the k-nearest neighbors of each point or by some other notion of nearness, see [3, 6, 7]. Spectral graph theory is also a cornerstone tool in the growing field of analysis on fractals [12, 10, 2, 11]. Let G = G(V,E) denote a graph where V = {xi} denotes a vertex set. The size of the vertex set, |V |, can be finite or infinite. Because data sets in applications are finite, we shall usually assume that G is a finite graph, i.e. |V | = N < ∞, unless stated otherwise. Although we assume the vertices V = {xi}i=1 to be fixed and indexed in a certain order, the mathematical theory that follows does not change if the names of the vertices are rearranged. The edge set, E, consists of ordered pairs that correspond to edges on a graph. If there is an edge between points x ∈ V and y ∈ V then we write x ∼ y. Hence, E = {(x, y) : x, y ∈ V and x ∼ y}. For any point x ∈ V , we define the degree of x, denoted dx, to be the number of edges connected to point x. In an undirected graph, the edge set E is symmetric, that is x ∼ y implies y ∼ x. In other words, we do not distinguish an incoming vs. outgoing orientation to any edge. Directed graphs arise when orientation is taken into consideration and the edge set E need not be symmetric; directed graphs will not be considered in this document. A graph, G, is connected if for any pair x, y ∈ V there exists a sequence of edges {(xi, xi+1)} i=0 ⊆ E such that x0 = x and xM = y. A connected component of G is a maximal subset of vertices that are all connected. Therefore, a connected graph has exactly one connected component. We consider functions defined on the vertex set f : V → R, xn 7→ f(xn). We shall occasionally use the shorthand notation f(n) = f(xn) which shall be clear in context.
