Claims:1. A method for sampling and reconstruction of band-limited signals by a graph parity check matrix technique, the method comprising processor implemented steps of:
classifying, by a band space classification technique, a plurality of band-limited graph signals into a null band and an occupied band, wherein the null band and the occupied band are obtained using a Graph Fourier Transform (GFT), and wherein the plurality of band-limited graph signals are acquired from a plurality of sources (201);
sampling, the plurality of band-limited graph signals classified, by performing a plurality of steps, wherein the plurality of steps comprise:
(i) selecting, an optimal sampling set, by the graph parity check matrix technique, wherein the optimal sampling set comprises a sampling set corresponding to the plurality of band-limited graph signals having a minimum reconstruction error (202(i)); and
(ii) extracting, a set of sampled signals, wherein the set of sampled signals comprise a set of low-dimension signals extracted from the optimal sampling set (202(ii)); and
reconstructing, by a graph syndrome technique, the set of sampled signals by performing a plurality of steps, wherein the plurality of steps comprise:
(i) extracting, one or more N-length signals from the set of sampled signals, wherein the one or more N-length signals are extracted by inserting a zero at one or more non-sampled points of the plurality of band-limited graph signals to estimate a graph syndrome (203(i));
(ii) determining, a set of values, based upon the one or more N-length signals, wherein the set of values comprise one or more non-sampled values estimated using the graph syndrome vector (203(ii)); and
(iii) reconstructing, based upon the set of values, the one or more N-length signals, wherein the one or more N-length signals correspond to a graphical structure (203(iii)).
2. The method of claim 1, wherein reconstructing the set of sampled signals is preceded by obtaining, using the GFT, a graph generator matrix and a graph parity check matrix, based upon the plurality of band-limited graph signals, to perform the sampling and the reconstruction of the one or more N-length signals.

3. The method of claim 1, wherein the set of sampled signals is represented as a difference between the plurality of band-limited graph signals and the one or more non-sampled values to reconstruct the set of sampled signals.

4. The method of claim 1, wherein the set of sampled signals reconstructed is represented in a linear framework based on a graph parity check matrix.

5. A system (100) for sampling and reconstruction of band-limited signals by a graph parity check matrix technique, the system (100) comprising:
a memory (102) storing instructions;
one or more communication interfaces (106); and
one or more hardware processors (104) coupled to the memory (102) via the one or more communication interfaces (106), wherein the one or more hardware processors (104) are configured by the instructions to:
classify, by a band space classification technique, a plurality of band-limited graph signals into a null band and an occupied band, wherein the null band and the occupied band are obtained using a Graph Fourier Transform (GFT), and wherein the plurality of band-limited graph signals are acquired from a plurality of sources;
sample, the plurality of band-limited graph signals classified, by performing a plurality of steps, wherein the plurality of steps comprise:
select, an optimal sampling set, by the graph parity check matrix technique, wherein the optimal sampling set comprises a sampling set corresponding to the plurality of band-limited graph signals having a minimum reconstruction error; and
extract, a set of sampled signals, wherein the set of sampled signals comprise a set of low-dimension signals extracted from the optimal sampling set; and
reconstruct, by a graph syndrome technique, the set of sampled signals by performing:
(i) extract, one or more N-length signals from the set of sampled signals, wherein the one or more N-length signals are extracted by inserting a zero at one or more non-sampled points of the plurality of band-limited graph signals to estimate a graph syndrome vector;
(ii) determine, a set of values, based upon the one or more N-length signals, wherein the set of values comprise one or more non-sampled values estimated using the graph syndrome vector; and
(iii) reconstruct, based upon the set of values, the one or more N-length signals, wherein the one or more N-length signals correspond a graphical structure.

6. The system (100) of claim 5, wherein the one or more hardware processors (104) are configured to obtain, using the GFT, a graph generator matrix and a graph parity check matrix, based upon the plurality of band-limited graph signals, to perform the sampling and the reconstruction of the one or more N-length signals.

7. The system (100) of claim 5, wherein the set of sampled signals is represented as a difference between the plurality of band-limited graph signals and the one or more non-sampled values to reconstruct the set of sampled signals.

8. The system (100) of claim 5, wherein the set of sampled signals reconstructed is represented in a linear framework based on a graph parity check matrix.
, Description:FORM 2

THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003

COMPLETE SPECIFICATION
(See Section 10 and Rule 13)

Title of invention:
SAMPLING AND RECONSTRUCTION OF BAND-LIMITED GRAPH SIGNALS BY GRAPH PARITY CHECK MATRIX TECHNIQUE

Applicant:
Tata Consultancy Services Limited
A company Incorporated in India under the Companies Act, 1956
Having address:
Nirmal Building, 9th Floor,
Nariman Point, Mumbai 400021,
Maharashtra, India

The following specification particularly describes the invention and the manner in which it is to be performed
TECHNICAL FIELD
The disclosure herein generally relates to sampling and reconstruction of band-limited graph signals by a graph parity check matrix technique, and, more particularly, to systems and methods for sampling and reconstruction of band-limited graph signals by a graph parity check matrix technique.

BACKGROUND
Limitations of discrete signal processing (DSP) in handling complex irregular structured data generated continuously from various sources such as social networks, biological networks etc. has led to the growth of other alternative fields such as graph signal processing (GSP). Graphs, inter-alia, provide a natural representation of data in a plurality of areas and the GSP broadly refers to processing of signals that resides on the vertices based upon the graph topology. The aim of sampling and reconstruction is to recover high dimensional signal (i.e., reconstruction) from a low dimensional signal (i.e., from a small subset of samples).
Band-limitedness comprises an essential key pre-requisite for sampling without significant information loss. Graphical models, inter-alia, consider inference and learning from structured dataset(s) by viewing data elements as random variables and reflecting their dependencies between each other with graph edges.
Similarly, even in the GSP, band-limitedness comprises an important pre-requirement for sampling and analogous to traditional systems and methods such as the DSP, band-limitedness of graph signals in the GSP is defined with the support of graph Fourier transform (GFT). In the transform domain, the GFT representation provides, inter-alia, an approximate optimal energy compaction of images when the graph is appropriately constructed, which is useful for compact compression.
Sampling set selection, that is, selecting appropriate subset(s) of vertices comprises an important step for unique and stable reconstruction. The traditional systems and methods for sampling and reconstruction computationally suffer in case of wider bandwidth(s). Further, the traditional systems and methods assume graph signal(s) to be bandlimited and then applies sampling and reconstruction to such band limited graph signals. Furthermore, even to sample and reconstruct the bandlimited graph signals, the traditional systems and methods implement in-band energy. Due to this, during the reconstruction process the native samples (i.e., the samples which are retained during sampling) also gets affected. This may not be preferable in practice because the reconstruction performance in the presence of noise may get severely affected.

SUMMARY
Embodiments of the present disclosure present technological improvements as solutions to one or more of the above-mentioned technical problems recognized by the inventors in conventional systems. For example, in one embodiment, a method for sampling and reconstruction of band-limited signals by a graph parity check matrix technique is provided, the method comprising: classifying, by a band space classification technique, a plurality of band-limited graph signals into a null band and an occupied band, wherein the null band and the occupied band are obtained using a Graph Fourier Transform (GFT), and wherein the plurality of band-limited graph signals are acquired from a plurality of sources; sampling, the plurality of band-limited graph signals, by performing a plurality of steps, wherein the plurality of steps comprise: (i) selecting, an optimal sampling set, by the graph parity check matrix technique, wherein the optimal sampling set comprises a sampling set corresponding to the plurality of band-limited graph signals having a minimum reconstruction error; and (ii) extracting, a set of sampled signals, wherein the set of sampled signals comprise a set of low-dimension signals extracted from the optimal sampling set; reconstructing, by a graph syndrome technique, the set of sampled signals by performing a plurality of steps, wherein the plurality of steps comprise: (i) extracting, one or more N-length signals from the set of sampled signals, wherein the one or more N-length signals are extracted by inserting a zero at one or more non-sampled points of the plurality of band-limited graph signals to estimate a graph syndrome vector; (ii) determining, a set of values, based upon the one or more N-length signals, wherein the set of values comprise one or more non-sampled values estimated using the graph syndrome vector; and (iii) reconstructing, based upon the set of values, the one or more N-length signals, wherein the one or more N-length signals correspond to a graphical structure; obtaining, using the GFT, a graph generator matrix and a graph parity check matrix, based upon the plurality of band-limited graph signals, to perform the sampling and the reconstruction of the one or more N-length signals; representing the set of sampled signals as a difference between the plurality of band-limited graph signals and the one or more non-sampled values to reconstruct the set of sampled signals; and representing the set of sampled signals reconstructed in a linear framework based on the graph parity check matrix.
In another aspect, there is provided a system for sampling and reconstruction of band-limited signals by a graph parity check matrix technique, the system comprising a memory storing instructions; one or more communication interfaces; and one or more hardware processors coupled to the memory via the one or more communication interfaces, wherein the one or more hardware processors are configured by the instructions to: classify, by a band space classification technique, a plurality of band-limited graph signals into a null band and an occupied band, wherein the null band and the occupied band are obtained using a Graph Fourier Transform (GFT), and wherein the plurality of band-limited graph signals are acquired from a plurality of sources; sample, the plurality of band-limited graph signals, by performing a plurality of steps, wherein the plurality of steps comprise: (i) select, an optimal sampling set, by the graph parity check matrix technique, wherein the optimal sampling set comprises a sampling set corresponding to the plurality of band-limited graph signals having a minimum reconstruction error; and (ii) extract, a set of sampled signals, wherein the set of sampled signals comprise a set of low-dimension signals extracted from the optimal sampling set; reconstruct, by a graph syndrome technique, the set of sampled signals by performing: (i) extract, one or more N-length signals from the set of sampled signals, wherein the one or more N-length signals are extracted by inserting a zero at one or more non-sampled points of the plurality of band-limited graph signals to estimate a graph syndrome vector; (ii) determine, a set of values, based upon the one or more N-length signals, wherein the set of values comprise one or more non-sampled values estimated using the graph syndrome vector; and (iii) reconstruct, based upon the set of values, the one or more N-length signals, wherein the one or more N-length signals correspond a graphical structure; obtain, using the GFT, a graph generator matrix and a graph parity check matrix, based upon the plurality of band-limited graph signals, to perform the sampling and the reconstruction of the one or more N-length signals; representing the set of sampled signals as a difference between the plurality of band-limited graph signals and the one or more non-sampled values to reconstruct the set of sampled signals; and representing the set of sampled signals reconstructed in a linear framework based on the graph parity check matrix.
In yet another aspect, there is provided one or more non-transitory machine readable information storage mediums comprising one or more instructions which when executed by one or more hardware processors causes the one or more hardware processor to perform a method for sampling and reconstruction of band-limited signals by a graph parity check matrix technique, the method comprising: classifying, by a band space classification technique, a plurality of band-limited graph signals into a null band and an occupied band, wherein the null band and the occupied band are obtained using a Graph Fourier Transform (GFT), and wherein the plurality of band-limited graph signals are acquired from a plurality of sources; sampling, the plurality of band-limited graph signals, by performing a plurality of steps, wherein the plurality of steps comprise: (i) selecting, an optimal sampling set, by the graph parity check matrix technique, wherein the optimal sampling set comprises a sampling set corresponding to the plurality of band-limited graph signals having a minimum reconstruction error; and (ii) extracting, a set of sampled signals, wherein the set of sampled signals comprise a set of low-dimension signals extracted from the optimal sampling set; reconstructing, by a graph syndrome technique, the set of sampled signals by performing a plurality of steps, wherein the plurality of steps comprise: (i) extracting, one or more N-length signals from the set of sampled signals, wherein the one or more N-length signals are extracted by inserting a zero at one or more non-sampled points of the plurality of band-limited graph signals to estimate a graph syndrome vector; (ii) determining, a set of values, based upon the one or more N-length signals, wherein the set of values comprise one or more non-sampled values estimated using the graph syndrome vector; and (iii) reconstructing, based upon the set of values, the one or more N-length signals, wherein the one or more N-length signals correspond to a graphical structure; obtaining, using the GFT, a graph generator matrix and a graph parity check matrix, based upon the plurality of band-limited graph signals, to perform the sampling and the reconstruction of the one or more N-length signals; representing the set of sampled signals as a difference between the plurality of band-limited graph signals and the one or more non-sampled values to reconstruct the set of sampled signals; and representing the set of sampled signals reconstructed in a linear framework based on the graph parity check matrix.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.

BRIEF DESCRIPTION OF THE DRAWINGS
The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together with the description, serve to explain the disclosed principles:
FIG. 1 illustrates a block diagram of a system for sampling and reconstruction of a plurality of band-limited graph signals by a graph parity check matrix technique, according to some embodiments of the present disclosure.
FIG. 2A through 2B is a flowchart illustrating the steps involved for the sampling and reconstruction of the plurality of band-limited graph signals by the graph parity check matrix technique, according to some embodiments of the present disclosure.
FIG. 3 shows an example graph constructed from data obtained from a plurality of sources to classify a plurality of band-limited graph signals into a null band and an occupied band by the graph parity check matrix technique, according to some embodiments of the present disclosure.
FIG. 4 shows a graphical representation of the plurality of band-limited graph signals classified into the null band and the occupied band, according to some embodiments of the present disclosure.
FIG. 5 shows a set of sampled signals obtained and represented graphically by implementing the graph parity check matrix technique, according to some embodiments of the present disclosure.
FIG. 6 shows a sampled signal reconstructed by inserting the set of values at non-sampled nodes (or locations), according to some embodiments of the present disclosure.
FIG. 7 shows a graphical comparison of sampled nodes obtained using a graph generator matrix and the graph parity check matrix technique, according to some embodiments of the present disclosure.

DETAILED DESCRIPTION OF EMBODIMENTS
Exemplary embodiments are described with reference to the accompanying drawings. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. Wherever convenient, the same reference numbers are used throughout the drawings to refer to the same or like parts. While examples and features of disclosed principles are described herein, modifications, adaptations, and other implementations are possible without departing from the spirit and scope of the disclosed embodiments. It is intended that the following detailed description be considered as exemplary only, with the true scope and spirit being indicated by the following claims.
The embodiments of the present disclosure provide systems and methods for sampling and reconstruction of band-limited signals by a graph parity check matrix technique, according to some embodiments of the present disclosure. The amount of data to be structured has grown drastically during the last decades thereby leading to a plurality of challenges for data science. The dimensionality of the information, i.e., the number of degrees of freedom, has greatly increased as well. Unfortunately, both the number of samples and the computations required to model the entire space grow exponentially with the dimensionality. However, in general, the data possesses a strong intrinsic structure, which prevents it to span the entire space. As a result, models do not need to be able to provide solutions for the whole space but only need to consider the structured subspace on which the data lives. For example, a classifier built from a digits dataset only needs to categorize deformed digits and not houses, cars, trees or any other images.
A convenient way to express this assumption mathematically is to consider that the data is sampled from a low-dimensional manifold embedded in a high-dimensional space. Graphs, inter-alia, provide a natural representation of data in a plurality of areas and the GSP broadly refers to processing of signals that resides on the vertices based upon the graph topology. A graph may be constructed or reconstructed usually in two different ways. First, it may be built using the data itself. In point clouds for instance, one or more nearest samples may be connected. Second, the graph may come naturally with the data.
Graphical models, inter-alia, consider inference and learning from structured dataset(s) by viewing data elements as random variables and reflecting their probabilistic dependencies between each other with graph edges. In the field of Graph Signal Processing (GSP), band-limitedness comprises an important pre-requirement for sampling and analogous to traditional systems and methods such as the DSP, band-limitedness of graph signals in the GSP is defined with the support of graph Fourier transform (GFT). The traditional systems and methods for sampling and reconstruction computationally suffer in case of wider bandwidth(s).
Hence, there is a need for a technology that provides for visualizing the process of sampling as removal of nodes akin to introducing erasures, due to which the graph syndromes of a sampled signal may lead to a set of significant values, which otherwise would be minuscule for a band-limited signal. Further, the technology must provide for a reconstruction of graph signals by making use of the set of significant values in the graph syndromes, and correspondingly the necessary and sufficient conditions for unique recovery may be obtained.
Referring now to the drawings, and more particularly to FIGS. 1 through 7, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments and these embodiments are described in the context of the following exemplary system and/or method.
FIG. 1 illustrates an exemplary block diagram of a system 100 for sampling and reconstruction of band-limited signals by a graph parity check matrix technique in accordance with an embodiment of the present disclosure. In an embodiment, the system 100 includes one or more processors 104, communication interface device(s) or input/output (I/O) interface(s) 106, and one or more data storage devices or memory 102 operatively coupled to the one or more processors 104. The one or more processors 104 that are hardware processors can be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor(s) is configured to fetch and execute computer-readable instructions stored in the memory 102. In an embodiment, the system 100 can be implemented in a variety of computing systems, such as laptop computers, notebooks, hand-held devices, workstations, mainframe computers, servers, a network cloud and the like.
The I/O interface device(s) 106 can include a variety of software and hardware interfaces, for example, a web interface, a graphical user interface, and the like and can facilitate multiple communications within a wide variety of networks N/W and protocol types, including wired networks, for example, LAN, cable, etc., and wireless networks, such as WLAN, cellular, or satellite. In an embodiment, the I/O interface device(s) can include one or more ports for connecting a number of devices to one another or to another server.
The memory 102 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes.
FIG. 2A through 2B, with reference to FIG. 1, illustrates an exemplary flow diagram of a method for the sampling and reconstruction of the band-limited signals by the graph parity check matrix technique in accordance with an embodiment of the present disclosure. In an embodiment the system 100 comprises one or more data storage devices of the memory 102 operatively coupled to the one or more hardware processors 104 and is configured to store instructions for execution of steps of the method by the one or more processors 104. The steps of the method of the present disclosure will now be explained with reference to the components of the system 100 as depicted in FIG. 1 and the flow diagram. In the embodiments of the present disclosure, the hardware processors 104 when configured the instructions performs one or more methodologies described herein.
According to an embodiment of the present disclosure, at step 201, the one or more hardware processors 104 perform a classification of a plurality of band-limited graph signals into a null band and an occupied band by a band space classification technique, and wherein the null band and the occupied band may be obtained using a Graph Fourier Transform (GFT). The plurality of band-limited graph signals may be acquired from a plurality of sources (like sensor(s)). The classification of the plurality of band-limited graph signals into the null band and the occupied band by implementing the band space classification technique with example scenarios has been discussed below in detail.
According to an embodiment of the present disclosure, graph signal(s) may now be defined. Let G =(V,?) denote a known, connected, undirected and a weighted graph comprising of N nodes indexed by a set V ={1,2,…,N} and connected by edges ?={(i,j,w_ij )},i,j ? V, where w_(i,j) denotes weight of the edge between i^th and j^th node and w_ii=0. In an embodiment, an adjacency matrix W is an NXN matrix with [W]_(i,j)=w_(i,j), with the assumption of the undirected graph W ? S^N. The degree of i^th node may be defined as d_i= ?_(j=1)^N¦?[W]_(i.j) ? and the degree matrix D=diag(d_1,d_2, … , d_N). In an embodiment, a graph Laplacian comprises a key matrix and may be defined as L=D-A. The graph shift operator S ? S^N, where [S]_(i,j) can be non-zero only if i=j or if (i,j)? ?. In an embodiment, S captures one or more local structures of the graphs and the graph shift operator may be selected either as a Laplacian matrix or as the adjacency matrix.
In an embodiment, the graph signal(s) comprises a scalar value assigned on each vertex or alternatively, may be a function f: V?R . Since S comprises a symmetric matrix, it admits an eigenvalue decomposition as below:
S=[u_1,…….,u_N ]diag(?_1,……,?_N )[u_1,…….,u_N ]^H
The eigenvectors and the eigenvalues U={u_1,…….,u_N } and {?_1,……,?_N} provide a notion of frequency in the context of the graphs. The GFT and inverse GFT of the graph signal f may be defined as f ^ =U^H f and f=Uf ^ respectively.
According to an embodiment of the present disclosure, the plurality of band-limited graph signals may now be defined. In an embodiment, the graph signal f may be defined as ?-band-limited if f ^_i=0 for all i with |?_i |> ?. In an embodiment, let R={1,2,…..,r) and the complementary set be R^c=V\R, where r denotes the number of eigenvalues that are less than ?. Thus, the GFT matrix may be expressed as U=[U_VR |U_(?VR?^c )], where U_VR and U_(?VR?^c ) comprise matrices of dimensions N×r and N×N-r. Using the U_VR, ?-band-limited graph signal f may be expressed as below:
f=?_(i=1)^r¦?u_i f ^_i ?=U_VR f ^_R equation (1)
In an embodiment, the set {u_1,u_2 …….,u_r} spans a vector space which may be referred as a Paley-Wiener space denoted by ?PW?_? (G), and comprising of all the ?-band-limited graph signals.
In an embodiment, the plurality of band-limited graph signals classified using the band space classification technique comprise the null band and the occupied band. In an embodiment, the null band comprises one or more graph frequencies having energy value(s) less than a predefined energy threshold, while the occupied band comprises one or more graph frequencies having energy value(s) more than the predefined energy threshold (example shown below).
The example implementation of the step 201 may now be performed and considered in detail. Suppose the plurality of band-limited graph signals are obtained from the plurality of sources (like a sensors) are as below:
[¦(-0.0611@0.0329@0.2090@-0.2335@-0.2241)]
Referring to FIG. 3, an example graph comprising of a set of five nodes and edge weights corresponding to the set of five nodes may be referred. As is known in the art, the example graph may be constructed using data acquired from the plurality of sources. Referring to FIG. 3 again, the edge weights between each of the nodes may be denoted as below:
(1,2) = 0.53
(1,3) = 1
(1,4) = 0.42
(1,5) = 0.48
(2,3) = 0.54
(2,4) = 0.98
(2,5) = 0.99
(3,4) = 0.42
(3,5) = 0.49
(4,5) = 0.99
In an embodiment, based upon the above example graph (that is, FIG. 3), a GFT matrix may be represented by matrix (1) as below:
[¦(-0.3921 &0.3944&-0.5792&0.0955&0.5833@-0.4907&0.4229&0.2398&-0.6727&-0.2563@-0.3954&-0.4057&0.5839&0.0122&0.5814@-0.4659&0.2512&0.2211&0.7261&-0.3790@-0.4817& -0.6618&-0.4660&-0.1049 &-0.3192)] – matrix (1)
Graph frequencies corresponding to the above example graph may be represented as below:
[¦(0.2112@0.9888@1.0000@1.3000@2.7776)] matrix (2)
Based upon the above GFT matrix and the graph frequencies, the plurality of band-limited graph signals may be classified into the null band and the occupied band, by implementing the band space classification technique, wherein the band space classification technique comprises initially obtaining, by the one or more hardware processors 104, a Graph Fourier Spectrum, by computing a product of the GFT matrix and the plurality of band-limited graph signals.
In an embodiment, the band space classification technique further comprises comparing a threshold value with absolute values (or a magnitude) of the Graph Fourier Spectrum. The threshold value may be selected based upon a maximum absolute value of the Graph Fourier Spectrum. In an example scenario, suppose the Graph Fourier Spectrum comprises of below matrix:
[¦(-0.2383@0.3126@-0.0003@-0.0016@-0.0063)]
The maximum absolute value of the above Graph Fourier Spectrum is 0.3126. Now, consider a scenario where 1/10 th of 0.3126 is taken as the threshold value. Based upon the threshold value, the plurality of band-limited graph signals into the null band and the occupied band, by comparing all the absolute values of the Graph Fourier Spectrum with the threshold value, wherein the absolute values of the Graph Fourier Spectrum are 0.2383, 0.3126, 0.0003, 0.0016 and 0.0063.
In an example implementation, based upon the threshold value, the plurality of band-limited graph signals obtained may be classified as below, wherein the graph frequencies (that is the graph frequencies referred in para 18 above) corresponding to the first two values, that is (0.2112 and 0.9888), correspond to the occupied band and the last three values, that is (1.000, 1.3000 and 2.7776), correspond to the null band.
[¦(-0.3921 &0.3944&-0.5792&0.0955&0.5833@-0.4907&0.4229&0.2398&-0.6727&-0.2563@-0.3954&-0.4057&0.5839&0.0122&0.5814@-0.4659&0.2512&0.2211&0.7261&-0.3790@-0.4817& -0.6618&-0.4660&-0.1049 &-0.3192)][¦(-0.0611@0.0329@0.2090@-0.2335@-0.2241)]=[¦(-0.2383@0.3126@-0.0003@-0.0016@-0.0063)]
In an example scenario, referring to FIG. 4, a graphical representation of the plurality of band-limited graph signals classified into the null band and the occupied band may be referred.
According to an embodiment of the present disclosure, the one or more hardware processors 104, at step 202(i) perform a sampling of the plurality of band-limited graph signals classified, by selecting an optimal sampling set by the graph parity check matrix technique, wherein the optimal sampling set comprises a sampling set corresponding to the plurality of band-limited graph signals having a minimum reconstruction error and then, at step 202(ii), extract a set of sampled signals, wherein the set of sampled signals comprise a set of low-dimension signals extracted from the optimal sampling set. The steps to perform the sampling of the plurality of band-limited graph signals by implementing the graph parity check matrix technique may now be discussed in detail.
According to an embodiment of the present disclosure, the one or more hardware processors 104, at step 202(i), select the optimal sampling set by a graph parity check matrix technique, wherein the optimal sampling set comprises a sampling set corresponding to the plurality of band-limited graph signals having a minimum reconstruction error. In an embodiment, let S? V denote a sampling set with cardinality, that is, |S|=d, and a complement sampling set S^c=V\S. In an embodiment, a uniqueness set on ?PW?_? (G) may be defined as below:
The sampling set S comprises the uniqueness set for the space ?PW?_? (G) if and only if f_S^1=f_S^2 implies f^1=f^2 for all f^1,f^2??PW?_? (G), wherein the f_S denotes the sampled signal set, that is, it comprises one or more element corresponding to the sampling set S.
In an embodiment, let L_2 (S^C) denote the space of all vectors in R^N that are zero at all places corresponding to S. In an embodiment, the necessary and sufficient condition for defining the uniqueness of the sampling set S for any signal f ??PW?_? (G) may be defined as below:
The sampling set S comprises the uniqueness set for the space ?PW?_? (G) if and only if f ??PW?_? (G)nL_2(S^C)={0}.
In an embodiment, let S_d be a matrix whose columns are indicator functions of S, sampling operator defined as S_d^T:R^N?R^d and a sampled sub-vector defined as f_S=S_d^T f. As is known in the art, some of the traditional systems and methods, for example, a frame operator theory implement equation (2) for reconstruction and the optimal sampling set selection.
f ^PW=?(U_VR (U_SR^H U_SR )-(U_PW ) ?()^(-1) U_SR^H f_S ) equation(2)
wherein the sub-matrix U_SR=S_D^T U_VR
It may be noted that the traditional systems and methods implement a plurality of methods for selecting the optimal sampling set which, inter-alia, comprise selecting appropriate rows from U_VR, since from the equation (2) it is clear that performance of selecting the optimal sampling set depends upon U_SR.
The proposed disclosure provides for selecting the optimal sampling set by implementing the graph parity check matrix technique, that is, by selecting the optimal sampling set based upon U_(?VR?^c ), wherein the U_(?VR?^c ) comprises a complementary matrix of U_VR.
In an embodiment, a graph parity check matrix is derived by implementing a graph syndrome technique. Both the graph syndrome technique and the graph parity check matrix technique may now be explained in detail.
Graph Syndrome Technique and the Graph Parity Check Matrix
According to an embodiment of the present disclosure, the graph syndrome of a signal f may be defined as:
m_f=?U^H?_(?VR?^c ) f equation (3)
Based upon the equation (3), it may be noted that for the ?U^H?_(?VR?^c ), if f?0 is assumed, then f??(?U^H?_(?VR?^c ) ) (that is, a null space of ?U^H?_(?VR?^c )) if and only if f ??PW?_? (G). The proposition implies that a graph syndrome m_f=0 for a perfect ?-band-limited signal. The matrices U_VR and U_(?VR?^c ) are analogous to generator and a parity check matrix respectively, and hence in the context of the graphs, the matrices U_VR and U_(?VR?^c ) may be referred to as a graph generator matrix and the graph parity check matrix respectively and the corresponding m_f as the graph syndrome of the graph signal f. In comparison with the traditional systems and methods, the graph parity check matrix helps in selecting the optimal sampling set and as well as proposes which two nodes (or columns) are to be removed amongst the plurality of band-limited graph signals.
In an example implementation, the graph generator matrix and the graph parity check matrix may be obtained as below (based upon the graph parity check matrix obtained and described in the previous paragraph), wherein the graph generator matrix is represented by matrix (3) and is obtained by transposing of the first two column of the matrix (1), and wherein the graph parity check matrix is represented by matrix (4) and is obtained by transposing of the last three rows of the matrix (1).
(¦(-0.3921&-0.4907@0.3944&0.4229@-0.5792&0.2398@0.0955&-0.6727@0.5883&-0.2653)) – matrix (3)
(¦(-0.3954&-0.4057&0.5839&0.0122&0.5814@-0.4659&0.2512&0.2211&07261&-0.3790@-0.4817&-0.6618&-0.4660&-0.1049&-0.3192)) – matrix (4)

In an example implementation, by implementing the proposed graph parity check matrix technique (with any greedy algorithm) on the matrix (4), an optimal non-sampling set (or locations) 1 and 3 and the corresponding optimal sampling set (or locations), that is, 2, 4 and 5 may be selected. For example, by selecting columns 1 and 3 (amongst all other choices of two columns in the matrix (4) above), lesser condition number is obtained. Hence, the optimal non-sampling set (or locations) 1 and 3 was selected.
Further, by implementing the graph parity check matrix technique below columns (nodes) have been removed. Therefore, below sub-matrix (that is matrix (6)) may be obtained from the matrix (4) after implementing the graph parity check matrix, wherein the matrix (6) comprise of columns corresponding to the optimal non-sampling set.
(¦(-0.3954&0.5839@-0.4659&0.2211@-0.4817&-0.4660)) – matrix (6)
According to an embodiment of the present disclosure, at step 202 (ii), the one or more hardware processors 104 extract the set of sampled signals, wherein the set of sampled signals comprise the set of low-dimension signals extracted upon the optimal sampling set. The sampling technique may be performed, inter-alia, by retaining one or more signals corresponding to the optimal sampling set and neglecting all others. In an example implementation, the set of sampled signals obtained based upon the matrix (5) (that is, the optimal sampling set) may be referred, wherein the set of sampled signals are represented by matrix (7). the
[¦(0.0329@-0.2335@-0.2241)] – matrix (7)
Referring to FIG. 5, the set of sampled signals obtained and represented graphically may be referred.
According to an embodiment of the present disclosure, at step 203, the set of sampled signals may be reconstructed by implementing the graph syndrome technique. The reconstruction may now be discussed in detail. At step 203(i), the one or more hardware processors 104, by implementing the graph syndrome technique, extract one or more N-length signals from the set of sampled signals, wherein the one or more N-length signals are extracted by inserting a zero at one or more non-sampled points (or nodes) of the plurality of band-limited graph signals to estimate a graph syndrome vector.
In an embodiment, a sampled signal f_S (amongst the set of sampled signals) may be expressed as:
S_d f_S=f-S_N^C f equation (4)
wherein, the S_N^C is a diagonal matrix of order NXN with diagonal entries of one’s corresponding to S^C and zeros corresponding to S. In an embodiment, the difference between S_d and S_N may be referred, wherein unlike S_N, S_d comprises ones corresponding to S and zeros corresponding to S^C and the columns corresponding to all zeros may be removed. It may be noted that by using the equation (4), the set of sampled signals may be represented as a difference between the plurality of band-limited graph signals and the one or more non-sampled values to reconstruct the set of sampled signals.
In an example implementation for the step 203(i), the one or more N-length signals are extracted by inserting a zero at one or more non-sampled points of the plurality of band-limited graph signals to estimate the graph syndrome vector may be as below:
(¦(-0.3954&-0.4057&0.5839&0.0122&0.5814@-0.4659&0.2512&0.2211&07261&-0.3790@-0.4817&-0.6618&-0.4660&-0.1049&-0.3192))[¦(0@0.0329@0@-0.2335@-0.2241)]=[¦(-0.1465@-0.0763@0.0742)]
Further, vector (that is, the graph syndrome vector) S_N^C f?L_2 (S^C) comprises zeros corresponding to sampling nodes in S. Using equation (3), the graph syndrome of the equation (4) may be expressed by equation (5) as below:
m_(f_S )=?U^H?_(?VR?^c ) S_d f_S equation (5)
In an embodiment, substituting the equation (4) in the equation (5), the graph syndrome may be expressed as below:
m_(f_S )=??-U?^H?_(?VR?^c ) S_N^C f equation (6)
=-U_(S^C R^C)^H f_(S^c ) equation (7)
In an embodiment, for expressing equation (6), below proposition has been used:
If f?0 is assumed, then f??(?U^H?_(?VR?^c ) ) (that is, a null space of ?U^H?_(?VR?^c )) if and only if f ??PW?_? (G).
For expressing equation (7), the structure of S_N^C may be implemented. It may be noted that U_(S^C R^C)^H and f_(s^c ) comprise one or more columns and one or more elements respectively, corresponding to the complementary set S^C.
According to an embodiment of the present disclosure, at step 203(ii), the one or more hardware processors 104 determine a set of values based upon the one or more N-length signals, wherein the set of values comprise one or more non-sampled values estimated using the graph syndrome vector. In an embodiment, the set of values, that’s is, the one or more non-sampled values may be obtained initially, by taking a product of a pseudo-inverse of the sub-matrix (that is, matrix (6) obtained by implementing the graph parity check matrix) and the graph syndrome vector.
In an example implementation of the step 203(ii), the sub-matrix or the matrix (6) (obtained by implementing the graph parity check matrix above) is:
(¦(-0.3954&0.5839@-0.4659&0.2211@-0.4817&-0.4660))
By taking the pseudo-inverse on the sub-matrix (6), the below matrix may be obtained:
[¦(-0.4953&-0.7274&-0.9658@0.8726&0.2332&-0.9419)]
In an embodiment, using the graph syndrome vector, the set of values may be obtained as:
[¦(-0.4953&-0.7274&-0.9658@0.8726&0.2332&-0.9419)][¦(-0.1465@-0.0763@0.0742)]=[¦(-0.0564@-0.2156)]
According to an embodiment of the present disclosure, at step 203 (iii), the one or more hardware processors 104 reconstruct, based upon the set of values, the one or more N-length signals, wherein the one or more N-length signals correspond to the graphical structure. In an embodiment, S_N^C=S_N^C S_N^C based upon the substitution of S_N^C=S_N^C S_N^C in the equation (6), the vector S_N^C f=-?(U?_(S^C R^C)^H )^† ?U^H?_(?VR?^c ) S_d f_S, wherein the (.)^† denotes Moore—Penrose Pseudoinverse. In an embodiment, by substituting m_(f_S ) from the equation (5), S_N^C f=-?(U?_(S^C R^C)^H )^† ?U^H?_(?VR?^c ) S_d f_S may be obtained.
Based upon S_N^C f=-?(U?_(S^C R^C)^H )^† ?U^H?_(?VR?^c ) S_d f_S and the equation (4), the reconstructed signal by implementing the graph syndrome technique f ^_GS may be expressed as below:
f ^_GS =S_d f_S+S_N^C f=S_d f_S-(U_(S^C R^C)^H )^† ?U^H?_(?VR?^c ) S_d f_S =?((I_N-(U_(S^C R^C)^H )^† ?U^H?_(?VR?^c ) S_d f_S))-(U_GS ) equation (8).
Referring to the equation (8), it may be noted that the set of sampled signals reconstructed are represented in a linear framework based on the graph parity check matrix. In an example implementation, implementing equation (8) based on the graph parity check matrix, below matrix may be obtained which establishes a linear relationship between the reconstructed signals and the set of sampled signals.
(¦(-0.6574&0.4330&0.2960@1.0000&0&0@-0.3278&0.2788&-0.7195@0&1.0000&0@0&0&1.0000))
In an example implementation for step 203(iii), referring to FIG. 6, a sampled signal (amongst the set of sampled signals) reconstructed may be referred, wherein the graph is reconstructed by inserting the set of values (determined in the step 203(ii)) at non-sampled nodes (or locations) in FIG. 5.
According to an embodiment of the present disclosure, referring to the equation (8) again, the difference between the equations (2) and (8) may be observed. The equation (2) relates the reconstructed signal and the sampled signal based upon U_VR and U_SR, the equation (8) performs the reconstruction of the sampled signal and represents the sampled signal based upon U_(?VR?^c ) and U_(S^C R^C ).
In an embodiment, based upon the equation (8) and the difference between the equations (2) and (8), corresponding to the set of sampled signals reconstructed using the graph syndrome technique, it may be noted that the reconstruction implemented using the graph syndrome technique is consistent and identical to the equation (2), that is, f ^_GS=f ^_PW. This is based on the proof wherein referring to the equation (7), it may be noted that only f ^_(s^c ) may be estimated by implementing the graph syndrome technique, and hence f ^_S=f_S implies a consistent reconstruction.
According to an embodiment of the present disclosure, based upon the equations (4) to (8), it may be noted that if f?0 is assumed, then f??PW?_? (G), the sampling set comprises a uniqueness set if and only if ?(U?_(S^C R^C)^H) is a full rank. This may now be considered in detail. Suppose S comprises the uniqueness set and referring to step 203(i), it may be noted that S_N^C f?L_2 (S^C). Further, referring to the step 202(i), it may be noted that as the sampling set S comprises the uniqueness set for the space ?PW?_? (G) if and only if f ??PW?_? (G)nL_2(S^C)={0}, it implies S_N^C f??PW?_? (G). If S_N^C f??PW?_? (G), and referring to step 203(i), it may be noted that if f?0 is assumed, then f??(?U^H?_(?VR?^c ) ) (that is, a null space of ?U^H?_(?VR?^c )) if and only if f ??PW?_? (G), then m_(f_S )?0, and hence ?(U?_(S^C R^C)^H) must be full rank (referring to the equation (7)).
In an embodiment, conversely, if ?(U?_(S^C R^C)^H) is full rank then it may also be observed that U_GS is also full rank. Based upon the equation (8), it may be observed that for any f_S^1=f_S^2, f ^_GS^1=f ^_GS^2, which based upon the below highlighted definition (referring to step 202(i)) implies S is the uniqueness set.
The sampling set S comprises the uniqueness set for the space ?PW?_? (G) if and only if f_S^1=f_S^2 implies f^1=f^2 for all f^1,f^2??PW?_? (G)
According to an embodiment of the present disclosure, referring to the theorem that if f?0 is assumed, then f??PW?_? (G), the sampling set comprises a uniqueness set if and only if ?(U?_(S^C R^C)^H) is a full rank (discussed and proved above in step 203(iii)), it may be noted in terms of the graph syndrome technique that, for any unique recovery, the graph syndrome technique must satisfy: (i) f??PW?_? (G), m_(f_S )?0 and (ii) f^1?f^2, m_(f_S^1 )?m_(f_S^2 ).
According to an embodiment of the present disclosure, simulation results, numerical results of the proposed disclosure and a comparison of the proposed disclosure with the traditional systems and methods may be considered. For experimental purposes, a random sensor graph comprising of N=50 nodes is generated. Further, for all experiments, the proposed disclosure generated a band-limited graph signal (amongst the plurality of band-limited graph signals) by assuming r=30 and hence the size of U_VR=50×30 and the size of U_(?VR?^c )=50×20.
In an embodiment, initially in the simulation, a comparison of the sampling sets obtained with two approaches, that is, the graph generator matrix and the graph parity check matrix, that is, with U_VR and U_(?VR?^c ) respectively was performed. In an embodiment, for both the cases the optimality criterion was maximizing the minimum eigenvalue of sampled matrices U_SR and U_(S^C R^C ) respectively and a greedy algorithm for selecting the sampling set. It may be recalled that using the graph parity check matrix U_(?VR?^c ), the set S^C may be obtained and subsequently, the sampling set may be obtained using V\S^C.
Referring to FIG. 7, the graph topology of N=50 nodes and the sampling nodes selected by implementing the two approaches (that is, the generator matrix and the graph parity check matrix) may be referred. Referring to FIG. 7 again, it may be noted that except for a few sampled locations, the other sampling node locations obtained with both approaches were identical. Referring to FIG. 7 yet again, the sampled nodes obtained with the graph generator matrix are depicted using ‘o’ and the sampled nodes obtained with the graph parity check matrix are depicted with ‘*’.
According to an embodiment of the present disclosure, the technical advantages of the proposed methodology may be considered. The proposed disclosure (methodology) provides for a visualization of the process of sampling as removal of nodes, which is akin to introducing erasures, due to which the graph syndromes of the sampled signal gives rise to a set of significant values, which otherwise would be minuscule for a band-limited signal. The traditional systems and methods for sampling and reconstruction computationally suffer in case of wider bandwidth(s). The reconstruction technique (that is, the proposed graph syndrome technique based reconstruction) makes use of the set of significant values in the graph syndrome technique and correspondingly the necessary and sufficient conditions for unique recovery and some key properties is provided. Thus, by visualizing the sampling of the band-limited graph signal as removal of nodes, which may be observed as an introduction of erasures, the proposed disclosure provides for a new method for the graph signal sampling and reconstruction. By connecting the graph syndrome to the band-stop spectrum, which may be manifested as a disturbance in the sampling process, the reconstruction method for the set of sampled signals has been provided by the proposed disclosure. Finally, based upon the simulation results and theories discussed in the steps 201 through 203, it may be concluded that the proposed method, besides provides for a robust reconstruction of the set of sampled signals.
In an embodiment, the memory 102 can be configured to store any data that is associated with the sampling and reconstruction of the band-limited signals by the graph parity check matrix technique. In an embodiment, the information pertaining to the plurality of band-limited graph signals, the occupied band and the null band, the set of sampled signals, the one or more N-length signals etc. and all information pertaining to the sampling and reconstruction is stored in the memory 102. Further, all information (inputs, outputs and so on) pertaining to the sampling and reconstruction of the plurality of band-limited signals may also be stored in the database, as history data, for reference purpose.
The written description describes the subject matter herein to enable any person skilled in the art to make and use the embodiments. The scope of the subject matter embodiments is defined by the claims and may include other modifications that occur to those skilled in the art. Such other modifications are intended to be within the scope of the claims if they have similar elements that do not differ from the literal language of the claims or if they include equivalent elements with insubstantial differences from the literal language of the claims.
It is to be understood that the scope of the protection is extended to such a program and in addition to a computer-readable means having a message therein; such computer-readable storage means contain program-code means for implementation of one or more steps of the method, when the program runs on a server or mobile device or any suitable programmable device. The hardware device can be any kind of device which can be programmed including e.g. any kind of computer like a server or a personal computer, or the like, or any combination thereof. The device may also include means which could be e.g. hardware means like e.g. an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or a combination of hardware and software means, e.g. an ASIC and an FPGA, or at least one microprocessor and at least one memory with software modules located therein. Thus, the means can include both hardware means and software means. The method embodiments described herein could be implemented in hardware and software. The device may also include software means. Alternatively, the embodiments may be implemented on different hardware devices, e.g. using a plurality of CPUs.
The embodiments herein can comprise hardware and software elements. The embodiments that are implemented in software include but are not limited to, firmware, resident software, microcode, etc. The functions performed by various modules described herein may be implemented in other modules or combinations of other modules. For the purposes of this description, a computer-usable or computer readable medium can be any apparatus that can comprise, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.
The illustrated steps are set out to explain the exemplary embodiments shown, and it should be anticipated that ongoing technological development will change the manner in which particular functions are performed. These examples are presented herein for purposes of illustration, and not limitation. Further, the boundaries of the functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternative boundaries can be defined so long as the specified functions and relationships thereof are appropriately performed. Alternatives (including equivalents, extensions, variations, deviations, etc., of those described herein) will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein. Such alternatives fall within the scope and spirit of the disclosed embodiments. Also, the words “comprising,” “having,” “containing,” and “including,” and other similar forms are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items. It must also be noted that as used herein and in the appended claims, the singular forms “a,” “an,” and “the” include plural references unless the context clearly dictates otherwise.
Furthermore, one or more computer-readable storage media may be utilized in implementing embodiments consistent with the present disclosure. A computer-readable storage medium refers to any type of physical memory on which information or data readable by a processor may be stored. Thus, a computer-readable storage medium may store instructions for execution by one or more processors, including instructions for causing the processor(s) to perform steps or stages consistent with the embodiments described herein. The term “computer-readable medium” should be understood to include tangible items and exclude carrier waves and transient signals, i.e., be non-transitory. Examples include random access memory (RAM), read-only memory (ROM), volatile memory, nonvolatile memory, hard drives, CD ROMs, DVDs, BLU-RAYs, flash drives, disks, and any other known physical storage media.
It is intended that the disclosure and examples be considered as exemplary only, with a true scope and spirit of disclosed embodiments being indicated by the following claims.