This paper proposes a method for vertex-wise aggregation sampling of a broad class of graph signals, designed to attain the best possible recovery based on the generalized sampling theory. This is achieved by designing a sampling operator by an optimization problem, which is inherently non-convex, as the best possible recovery imposes a rank constraint. An existing method for vertex-wise aggregation sampling is able to control the number of active vertices but cannot incorporate prior knowledge of mandatory or avoided vertices. To address these challenges, we formulate the operator design as a problem that handles a constraint on the number of active vertices and prior knowledge on specific vertices for sampling, mandatory inclusion or exclusion. We transformed this constrained problem into a difference-of-convex (DC) optimization problem by using the nuclear norm and a DC penalty for vertex selection. To solve this, we develop a convergent solver based on the general double-proximal gradient DC algorithm. The effectiveness of our method is demonstrated through experiments on various graph signal models, including real-world data, showing superior performance in the recovery accuracy compared to existing methods.
Figures & tables
Notations
Definitions
X
a set
x
a vector
xi,[x]i
the i -th element of x
∥x∥2
the ℓ2 norm of x , ∥x∥2:=∑ixi2
X
a matrix
x(i),[X](i)
the i -th row vector of X
Table 1: Notations and Definitions.
Subspace
Smoothness
Stochastic
P
A⊤
ΣF−1VF⊤
Q
Table 2: Definitions of the Matrix P for Each Prior. The Following Definitions Are Used: F=UFΣFVF⊤ and Γx=Q⊤Q .
Prior
λ
δ
γ1(0)
γ2(0)
Subspace (SB)
1.05
10−1
10−3
10−5
Smoothness (SM)
5.1
10−1
10−2
10−2
Stochastic (ST)
0.75
10−6
10−3
10−5
Table 3: Parameters for the Proposed Method.
Signal Prior
SP [ 2 ]
AVM [ 24 ]
GSSS [ 21 ]
ScFGSS [ 46 ]
Design (i)
Design (ii)
Design (iii)
SB (PGS)
−19.672
−18.474
−612.924
−604.539
−606.181
−608.050
−601.380
+ noise
−14.896
−13.730
−27.669
−38.753
−37.838
−22.354
−16.717
SM (GMRF)
−23.630
−6.125
−27.559
−27.739
−27.679
−27.395
−27.392
+ noise
−18.003
−4.600
−22.608
−26.960
−27.374
−26.428
−25.900
ST (GMRF)
−20.758
−9.036
−25.243
−26.235
−26.705
−26.617
−26.572
+ noise
−15.137
−6.158
−23.972
−25.933
−25.553
−25.373
−25.368
Table 4: Average MSEs in Decibel of the Recoveries for 20 Independent Runs on each Method.
Figure 1: An example of sampling and recovery experiment on a PGS graph signal on a random sensor graph. Fig. ( 1(a) ) shows the original PGS signal. Figs. ( 1(b) )-( 1(h) ) show the recovered signals from the noiseless sampled signals, and Figs. ( 1(i) )-( 1(o) ) show the recovered signals from the noisy sampled signals. The results in MSE are expressed in decibels, where smaller values indicate better recovery accuracy. The best and second best results in each case are in bold and underlined, respectively.
Signal Prior
Design (i)
Design (ii)
Design (iii)
SB (PGS)
24.20
33.60
31.50
SM (GMRF)
30.75
31.10
31.00
ST (GMRF)
31.85
31.85
32.00
Table 5: Average Number of Active Vertices by the Proposed Method for 20 Independent Runs.
Prior
λ
δ
γ1(0)
γ2(0)
Smoothness (SM)
1.2
10−6
10−2
10−5
Stochastic (ST)
0.33
10−6
10−2
10−5
Table 6: Parameters for the Proposed Method.
Figure 2: Sampling operators designed by the proposed method for the graph signal in Fig. 1 . Zero values are shown in black.
Figure 3: Examples of convergence behavior of the proposed method (Design (i)): objective function values and relative errors.
Prior
SP
AVM
GSSS
ScFGSS
Ours
SM
−29.429
−29.111
−42.689
−44.765
−44.065
+ noise
−18.833
8.075
−33.751
−40.807
−40.842
ST
−
−
−48.247
−67.708
−68.279
+ noise
−
−
−39.838
−61.148
−64.416
Table 7: Average MSEs in Decibel of the Recoveries for Monthly Average Temperature at 110 Stations in Switzerland.
Figure 4: Signal recovery results for the average temperature of Switzerland in October with assuming the stochastic prior. Fig. ( 4(a) ) shows the original temperature. Figs. ( 4(b) )-( 4(f) ) show the recovered temperatures. The best result is in bold.