thgsp.sampling

Efficient Sampling Set Selection

ess(operator, M, k=2)[source]

An efficient sampling set selection method for bandlimited graph signals 1.

Parameters

  • operator (SparseTensor) – The chosen variation operators, e.g., graph normalized Laplacian.

  • M (int) – The number of desired sampled nodes.

  • k (int) – The proxy order. Refer to the literature for details.

Returns

S – A list containing sampled nodes with the sampling order

Return type

list

References

1

Aamir Anis, et al., “Efficient sampling set selection for bandlimited graph signals using graph spectral proxies,” IEEE TSP, 2016.

recon_ess(y, S, U, bd, **kwargs)[source]

Naive implementation of ESS sampling reconstruction.

Parameters

  • y (Tensor) – Dense Shape: (N)

  • S (List) – The sampling set

  • U (Tensor) – Dense (N, bd)

  • bd (int) – The bandwidth of target signal

  • kwargs (dict) – The optional arguments of xp.linalg.lstsq

Returns

f_hat – The reconstructed signal

Return type

Tensor

Fast Graph Sampling Set Selection

bsgda(spm: torch_sparse.tensor.SparseTensor, K: int, mu: float = 0.01, epsilon: float = 1e-05, p_hops: int = 12, boost=True) → Tuple[List, float][source]

A fast deterministic vertex sampling algorithm on Gershgorin disc alignment and for smooth graph signals 2.

Parameters

  • spm (SparseTensor) – The sparse adjacency matrix.

  • K (int) – The desired number of sampling nodes.

  • mu (float) – The parameter for graph Laplacian based signal reconstruction. Refer to Eq(7) 2 for the details.

  • epsilon (float) – The numerical precision for binary search (1e-5 by default

  • p_hops (int) – Estimate the coverage subsets(refer to Definition 1 2) within the p_hops neighborhood.

  • boost (bool) –

Returns

  • sampled_nodes (List) – The sampled nodes.

  • left (float) – The approximate threshold T, i.e., the lower bound of the eigenvalues of \(\mathbf{H}^{\top} \mathbf{H}+\mu \mathbf{L}\).

References

2(1,2,3)

Y. Bai, et al., “Fast graph sampling set selection using Gershgorin disc alignment,” IEEE TSP, 2020.

Random sampling of bandlimited signals

estimate_lk(G, k, num_estimation=1, num_rv=None, epsilon=0.01, lmin=None, lmax=None, return_coherence=True, order=30, lap_type='comb', verbose=False)[source]

Estimate the optimal distribution according to which the bandlimited graph signals are sampled 3 .

Parameters

  • G (GraphBase) – The graph

  • k (int) – The k-th smallest eigenvalue of graph Laplacian

  • num_estimation (int) – The number of times the estimation of \(\lambda_{k}\) is going to run

  • num_rv (int, None) – The number of random vectors used

  • epsilon (float) – The tolerance of binary search to find approximated \(\lambda_{k}\)

  • lmin (float) – The smallest frequency of graph Laplacian

  • lmax (float) – The largest frequency of graph Laplacian

  • return_coherence (bool) – If True, return the estimated square of graph local cumulative coherence 3 of all nodes

  • order (int) – The order of the Chebyshev approximation

  • lap_type (str) – comb, sym, and rw represent combinatorial, symmetric normalized, and random-walk normalized Laplacian, separately

  • verbose (bool) –

Returns

  • lambda_k (float) – The eventual estimated k-th smallest graph frequency

  • cum_coh (Tensor or(None)) – If return_coherence is True , return the estimated graph local cumulative coherence 3 of every node, otherwise None

References

3(1,2,3,4)

G. Puy, et al., “Random sampling of bandlimited signals on graphs,” Applied and Computational Harmonic Analysis, 2018.

rsbs(G: thgsp.graphs.core.GraphBase, M: int, k: Optional[int] = None, num_estimation: int = 1, num_rv: Optional[int] = None, epsilon: float = 0.01, lmin: Optional[float] = None, lmax: Optional[float] = None, order: int = 30, lap_type: str = 'comb', return_list: bool = False, verbose: bool = False)[source]

Random sampling algorithm for bandlimited signals 3 .

Parameters

  • G (GraphBase) – The graph to be handled

  • M (int) – The number of vertices to be sampled

  • k (int, optional) – The k-th smallest eigenvalue of graph Laplacian. If None, k = M.

  • num_estimation (int) – The number of times the estimation of \(\lambda_{k}\) is going to run

  • num_rv (int, None) – The number of random vectors used

  • epsilon (float) – The tolerance of binary search to find approximated \(\lambda_{k}\)

  • lmin (float) – The smallest frequency of graph Laplacian

  • lmax (float) – The largest frequency of graph Laplacian

  • return_list (bool) – If True, return List otherwise a Tensor having the same dtype and device as the input graph G .

  • order (int) – The order of the Chebyshev approximation

  • lap_type (str) – comb, sym, and rw represent combinatorial, symmetric normalized, and random-walk normalized Laplacian, separately.

  • verbose (bool) –

Returns

  • sampled_nodes (List, Tensor) – The sampling set

  • cum_coh (Tensor) – The sampling possibilities of all nodes

Eigen-decomposition free sampling

fastgsss(G: thgsp.graphs.core.GraphBase, M, bandwidth, nu=75.0, cheby=True, order=12, verbose=False)[source]

FastGSSS proposed in 4 .

Parameters

  • G (GraphBase) – The graph whose signals are to sample

  • M (int) – The desired number of sampled nodes

  • bandwidth (int) – The estimated bandwidth of original signals

  • nu (float) – The parameter controlling the width of the heat diffusion filter kernel.

  • cheby (bool) – If True, compute the localization operator with Chebyshev approximation; otherwise compute it from a direct expensive EVD.

  • order (int) – The order of Chebyshev approximation.

Returns

  • S (List) – The sample set

  • T (SparseTensor) – The localization operator

References

4

A. Sakiyama, Y. Tanaka, T. Tanaka, and A. Ortega, “Eigendecomposition-free sampling set selection for graph signals,” IEEE TSP, 2020.

recon_fastssss(y, S, T, order, sd=0.5)[source]

A primary implementation of reconstruction method associated with “FastSSS” sampling algorithm.

Parameters

  • y (Tensor) – The measurements on sampling set :obj:S:. If the localization operator T has a density greater than the threshold sd, y has a shape of either (M,)，(M,1)，or (M,C); otherwise y could only be either (M,) or (M,1).

  • S (List) – A list consisting of all indices of sampled nodes.

  • T (Tensor, SparseTensor) – The localization operator

  • order (int) –

  • sd (float) – The threshold of T’s density that controls when we use a dense or sparse linear solver.

Returns

The signal recovered from the measurements y .

Return type

Tensor

Utils

construct_sampling_matrix(N, S, dtype=None, device=None, layout='csr', return_ts=False)[source]

Construct the sampling matrix \(\mathbf{H} \in\{0,1\}^{M \times N}\) defined as follows.

\[\begin{split}\mathbf{H}_{i j}= \begin{cases}1, & j=\mathcal{S}_{i} \\ 0, & \text { otherwise } \end{cases}\end{split}\]
Parameters

  • N (int) – The total number of nodes

  • S (list, array, torch.Tensor) – The 1-D list of sampled nodes.

  • dtype (torch.dtype, optional) – The dtype

  • layout (str) – The memory layout of the generated sparse matrix. One of (“csc”, “csr”, “coo”).

  • device (torch.device, str, optional) – If True and cupy is installed, use cupy`as backend; otherwise `scipy.

  • return_ts (bool,) – If False, return scipy.sparse.spmatrix of device is GPU else ‘cupyx.scipy.sparse.spmatrix’

Returns

H – The (M,N) scipy sparse matrix with layout format

Return type

spmatrix