Uncertainty Principle for Vertex-Time Graph Signal Processing Yanan Zhao, Xingchao Jian, Feng Ji, Wee Peng Tay, Antonio Ortega Abstract We present an uncertainty principle for graph signals in the vertex-time domain, unifying the classical time-frequency and graph uncertainty principles within a single framework. By defining vertex-time and spectral-frequency spreads, we quantify signal localization across these domains. Our framework identifies a class of signals that achieve maximum concentration in both the spatial and temporal domains. These signals serve as fundamental atoms for a new vertex-time dictionary, enhancing signal reconstruction under practical constraints, such as intermittent data commonly encountered in sensor and social networks. Furthermore, we introduce a novel graph topology inference method leveraging the uncertainty principle. Numerical experiments on synthetic and real datasets validate the effectiveness of our approach, demonstrating improved reconstruction accuracy, greater robustness to noise, and enhanced graph learning performance compared to existing methods. I Introduction The uncertainty principle for signal processing, first developed by Slepian, Landau, and Pollack [ 1 , 2 ] , describes the trade-off between a signal’s time and frequency localization. It states that no signal can be simultaneously arbitrarily well localized in both domains. Prolate spheroidal wave functions (PSWFs) [ 3 , 4 , 5 , 6 ] embody this balance by maximizing a signal’s energy within a finite time interval while remaining bandlimited to a specified frequency range, making them an effective basis for representing or processing signals under simultaneous time-frequency constraints. Similarly, uncertainty principles for graph signal processing (GSP) have been developed in [ 7 , 8 , 9 , 10 ] and more recently in [ 11 , 12 ] , capturing the trade-off between localization in the vertex and (graph) spectral domains. Early formulations of graph uncertainty principles, such as [ 7 ] , define signal spread using distance-based metrics over the graph, measuring localization in the vertex and spectral domains. However, this approach depends on a specific choice of graph distance, such as the geodesic distance [ 13 ] , resistance distance [ 14 ] , or diffusion distance [ 15 ] , which introduces inherent limitations. To address this, [ 16 ] introduced a distance-independent definition of spread inspired by the work of Slepian, Landau, and Pollack [ 3 , 4 , 1 ] on prolate spheroidal wave functions. Their approach characterizes vertex and spectral spreads without relying on specific distances, defining a principle that measures energy concentration across vertex and spectral subsets. Notably, [ 16 ] observes that, unlike the uncertainty principle for time-frequency localization, certain graph signals can be perfectly localized in both domains. By defining a feasible boundary for the vertex and spectral spreads, a class of signals maximally concentrated in both the vertex and spectral domains can be identified. Further extensions of the uncertainty principle have been made in the context of the graph linear canonical transform (GLCT) domain [ 17 ] , leading to a sampling theory for the GLCT and the derivation of optimal sampling operators based on the uncertainty principle. Traditional GSP focuses mainly on analyzing information within the vertex domain. In some applications, however, each vertex is associated with a discrete or continuous time signal. To address such scenarios, the works [ 18 , 19 , 20 , 21 ] have extended classical GSP to handle vertex-time signals. This includes tools such as the vertex-time Fourier transform, vertex-time filters, joint harmonic analysis, and vertex-time signal recovery. To enable localized representations in the vertex-time domain , redundant vertex-time dictionaries [ 22 , 23 ] have also been developed, including the short time-vertex Fourier transform (STVFT) and the spectral time-vertex wavelet transform (STVWT) . Despite these advances, existing methods struggle to handle sparse, irregular, or constrained observations, as commonly encountered in real-world scenarios such as sensor networks. Some specific challenges are: (i) temporal irregularity , where sensors record at uneven or intermittent intervals due to limited battery, event-triggered sampling, or communication delays; (ii) spatial sparsity , where only a subset of sensors report at a given time because others are shut down, fail, or undergo maintenance; (iii) joint spatio–temporal irregularity , where the set of reporting sensors changes over time, leaving irregular coverage of the vertex–time domain. Conventional approaches like STVFT and STVWT rely on fixed-time windowing or wavelet bases that assume regularly spaced coverage of the vertex–time domain and thus lack the adaptability to capture signal energy concentrated over irregular or data-dependent subsets of vertices and time intervals. These limitations are especially problematic in sensor networks, where solar-powered devices may only operate during daylight or harsh environments may force intermittent operation, all of which reduce data availability and hinder reconstruction. In this work, we refer to the “graph frequency” domain as the spectral domain, and the “time frequency” domain as simply the frequency domain. Addressing the above challenges requires signal processing and representation methods that account for the localization trade-offs between the vertex-time and spectral-frequency domains. While uncertainty principles for the vertex domain versus the spectral domain in GSP have been established, none address signals defined over irregular vertex–time domains. To close this gap, our objective is to establish an uncertainty principle that rigorously characterizes the localization trade-offs in the vertex–time domain versus the spectral-frequency domain, which in turn provides the theoretical foundation for designing energy-concentrated dictionaries and graph learning. (a) Jul 29, 2020–Jul 30, 2021 (b) Jul 31, 2021–Aug 1, 2022 Fig. 1 : The number of reported cases across counties and days from July 29, 2020, to August 1, 2022, for the Covid-19 dataset. To illustrate the need for energy-concentrated representations, consider the Covid-19 dataset 1 1 1 https://github.com/TorchSpatiotemporal/tsl , which records reported cases across California’s 58 counties from July 29, 2020, to August 1, 2022. Figure 1 shows that case counts are highly localized, with energy concentrated in specific counties (e.g., 2, 5, 14, 15, 57) and during particular time intervals (e.g., days 100 to 200). In addition, the dataset contains days with zero reported cases in some counties, which often reflect delayed or missing reporting rather than a true absence of cases. These patterns demonstrate that the signal energy is not uniformly distributed in time or across vertices, but instead occupies a limited subset of the vertex-time domain. This highlights the importance of constructing vertex-time dictionaries that can efficiently capture such localized energy concentrations. However, existing approaches such as STVFT and STVWT rely on fixed bases that are not tailored to irregular or data-driven supports, limiting their ability to represent signals concentrated on specific subsets in the joint vertex-time domain. In this work, we address this limitation by first defining the uncertainty principle in the vertex-time domain and then leveraging it to design basis functions that maximize energy concentration over selected subsets of vertices and time intervals, enabling efficient signal representation and reconstruction under practical, constrained observation scenarios. In this paper, we focus on energy-based localization over the vertex-time domain, while acknowledging the existence of alternative localization metrics [ 24 , 25 , 26 ] . Unlike prior works such as [ 18 , 19 , 21 ] that operate in the discrete-time domain with signals defined at fixed time steps, our framework adopts the continuous-time domain introduced in [ 20 ] . Discrete-time formulations face inherent limitations when node sampling is irregular. Using a common discrete sampling rate enforces temporal alignment but requires the rate to match the most densely sampled node, resulting in a high global rate and many missing entries for sparsely observed nodes. Conversely, assigning independent sampling rates to each node better reflects their observation patterns, but this approach leads to temporal misalignment and complicates cross-node comparisons. A continuous-time formulation overcomes these issues by defining signals on a shared temporal axis and interpreting discrete observations as samples from an underlying continuous process. This provides a unified representation that naturally accommodates asynchronous and heterogeneous sampling without resampling, while maintaining consistent alignment across nodes and enabling a precise characterization of energy concentration over irregular subsets of the vertex–time domain. Building on this perspective, we develop an uncertainty principle to understand the trade-offs between signal localization in the vertex-time and spectral-frequency domains. This principle underpins two main applications: (i) the design of basis functions that are maximally energy-concentrated over specific vertex–time subsets, and (ii) a graph learning approach that maximizes spectral–frequency energy concentration while respecting vertex–spectral localization trade-offs, which existing methods [ 27 , 28 ] typically ignore. Instead of naively extending the vertex-domain framework in [ 16 ] , which considers signal localization only in the vertex domain, by simply including the entire time interval, our new framework captures the localized behavior of signals across both vertices and time intervals by focusing on specific subspaces of functions defined on the joint vertex-time domain. This approach leads to a better understanding of how signals evolve over space and time, and to a more accurate and efficient representation of signals. The main contributions of this paper are summarized as follows: 1. We formulate a generalized uncertainty principle in the vertex-time domain that unifies and extends existing graph [ 16 ] and continuous-time formulations [ 1 ] through a subspace-based localization measure, encompassing the classical subset-based notions [ 16 , 2 ] as special cases. 2. We identify a class of vertex-time graph signals that achieve maximal concentration in both the vertex-time and spectral-frequency domains . These signals serve as fundamental atoms in a vertex-time dictionary for signal reconstruction. We derive their localization properties and outline dictionary construction and optimization for improved reconstruction accuracy. 3. We propose a new graph learning approach that maximizes energy concentration in the spectral-frequency domain . This method captures the intrinsic signal structure while adhering to the vertex-spectral localization trade-off dictated by the uncertainty principle. 4. We evaluate our vertex-time dictionary learning and graph learning methods on both synthetic and real datasets . Results demonstrate improved reconstruction accuracy, achieving an average gain of 4 dB, and superior noise robustness, maintaining stable performance even under noise levels as low as 0 dB, compared to existing dictionary learning methods. Additionally, our method improves graph inference precision by 4.7% over existing graph learning approaches. This paper extends our earlier work in [ 29 ] , where we first introduced a generalized uncertainty principle that unifies existing principles for graph and continuous-time signals. In this paper, we build upon that foundation by providing a detailed characterization of localization trade-offs in the vertex–time and spectral–frequency domains. Leveraging these insights, we propose a new energy-concentrated vertex–time dictionary for signal reconstruction and introduce a new graph learning approach that captures intrinsic signal structures while explicitly respecting the localization trade-offs dictated by the uncertainty principle. These extensions address the main limitations of our earlier work, namely the lack of a systematic study of concrete localization conditions (e.g., when perfect vertex and time localization is achievable) and the absence of concrete applications of the established principle. The remainder of this paper is organized as follows. section II develops the uncertainty principle for vertex-time graph signals. Compared to our earlier work [ 29 ] , section III expands the discussion by proposing a new vertex-time dictionary learning method based on this principle for signal reconstruction, while section IV introduces a new graph topology inference method that was not included in [ 29 ] . Numerical results are presented in section V , followed by concluding remarks in section VI . Notations. Scalars and scalar-valued functions are denoted by lowercase letters (e.g., x ), vectors and vector-valued functions by bold lowercase (e.g., \mathbf{x} ), and matrices by bold uppercase (e.g., \mathbf{A} ). The sets of real, complex, and integer numbers are denoted by \mathbb{R} , \mathbb{C} , and \mathbb{Z} , respectively. The space of square-integrable functions on a domain \Omega is L^{2}(\Omega) , and \|\cdot\| denotes its norm when unambiguous. The symbols \|\cdot\|_{1} , \|\cdot\|_{2} , and \|\cdot\|_{F} denote the L^{1} , L^{2} , and Frobenius norms. The Kronecker delta is \delta_{ij} , where i and j denote integer indices. The tensor product is \otimes , \diag(\mathbf{v}) is the diagonal matrix with diagonal \mathbf{v} , and transpose is denoted by (\cdot)^{\mathop{\intercal}} . II Uncertainty Principle for Vertex-time Graph Signals In this section, we establish an uncertainty principle for vertex-time graph signals. We adopt and extend the definition of spread introduced in [ 16 ] to quantify the localization of vertex-time graph signals in the vertex-time and spectral-frequency domains. II-A Fourier transforms Throughout this paper, we consider undirected graphs \mathcal{G}=(\mathcal{V},\mathbf{A}) consisting of a set of N vertices \mathcal{V}=\{1,2,\dots,N\} , along with a set of weighted edges with adjacency weight matrix \mathbf{A}=[a_{ij}]_{i,j\in\mathcal{V}} , such that a_{ij}>0 , if vertex i and j are connected by an edge, or a_{ij}=0 , otherwise. We assume that \mathcal{G} is a connected weighted graph with no self-loops. The graph Laplacian matrix is given by \mathbf{L}=\mathbf{D}-\mathbf{A} , where \mathbf{D} is the degree matrix. We take \mathbf{L} to be the graph shift operator (GSO). The graph Fourier transform (GFT) of a graph signal \mathbf{x}\in\mathbb{R}^{N} [ 30 , 31 , 32 , 33 , 34 , 35 ] is given by \displaystyle\widehat{\mathbf{x}}=\mathbf{U}{{}^{\mathop{\intercal}}}\mathbf{x} (1) where \mathbf{U} is the unitary matrix whose columns are the Laplacian eigenvectors. A vertex-time graph signal f is a map \mathcal{V}\times\mathcal{T}\rightarrow\mathbb{C} , defined by (v,t)\mapsto f(v,t) , where \mathcal{V} and \mathcal{T}=\mathbb{R} represent the vertex and time domains, respectively [ 20 , 23 , 19 ] . We denote the space of vertex-time graph signals as L^{2}\left(\mathcal{V}\times\mathcal{T}\right) . For f\in L^{2}(\mathcal{V}\times\mathcal{T}) , the joint Fourier transform (JFT) is defined as [ 20 ] : \displaystyle\mathcal{F}_{f}(\lambda_{k},\omega)=\langle f,\mathbf{u}_{k}\otimes e^{\mathfrak{i}\mkern 1.0mu\omega t}\rangle,\;\;\text{for}\;\;k=1,\dots,N, (2) where \lambda_{k} and \mathbf{u}_{k} are the k -th eigenvalue and eigenvector of \mathbf{L} , respectively, \otimes is the tensor product, and \mathfrak{i}\mkern 1.0mu=\sqrt{-1} . The JFT maps the signal f in L^{2}(\mathcal{V}\times\mathcal{T}) to a signal in L^{2}(\Lambda\times\Omega) , where \Lambda=\{\lambda_{1},\dots,\lambda_{N}\} and \Omega=\mathbb{R} are referred to as the spectral and frequency domains, respectively. The JFT generalizes both the GFT and the classical Fourier transform (FT) . Specifically, the JFT reduces to the GFT , which maps a graph signal from \mathcal{V} to \Lambda , when f is evaluated at a fixed time instance, and to the FT mapping a temporal signal from \mathcal{T} to \Omega when \mathcal{V} is a singleton. Readers are referred to [ 20 ] for more details on generalized graph signal processing (GGSP) . II-B Vertex-time and spectral-frequency spreads In this work, we adopt a general concept of localization for square-integrable vertex-time graph signals based on energy concentration over subspaces of L^{2}(\mathcal{V}\times\mathcal{T}) . This approach extends the framework introduced in [ 16 ] for graph signals. Definition 1 (Vertex-time projection) . Let \mathcal{H}_{\VT}\subseteq L^{2}(\mathcal{V}\times\mathcal{T}) be a closed subspace. The vertex-time projection operation \Pi_{\VT} is the orthogonal projection onto \mathcal{H}_{\VT} , where \Pi_{\VT}f\in\mathcal{H}_{\VT} for any vertex-time graph signal f\in L^{2}(\mathcal{V}\times\mathcal{T}) . The operator \Pi_{\VT} is Hermitian and idempotent, i.e., (\Pi_{\VT})^{2}=\Pi_{\VT} . The following are special cases following 1 : 1. Define \mathcal{H}_{\VT}:=\{f\in L^{2}(\mathcal{V}\times\mathcal{T})\nonscript\,:\allowbreak\nonscript\,\mathopen{}f(v,t)=0~\text{for}~(v,t)\notin\mathcal{S}\} for a vertex–time support subset \mathcal{S}\subseteq\mathcal{V}\times\mathcal{T} . The projection reduces to the classical vertex-time limiting operator: \displaystyle\Pi_{\VT}f=\Pi_{\mathcal{S}}f:=\begin{cases}f(v,t)&\ \text{if}\ (v,t)\in~\mathcal{S},\\ 0&\ \text{otherwise}.\end{cases} (3) Specific examples include: a) Vertex-limiting projection: When the signal is defined over the vertex set \mathcal{V} at a fixed time t_{0} , we have f\in L^{2}(\mathcal{V}\times\{t_{0}\})\cong L^{2}(\mathcal{V}) , which naturally reduces to a graph signal f(v)=f(v,t_{0})\in\mathbb{C} for each v\in\mathcal{V} . In this case, a subset \mathcal{S}=\mathcal{V}^{\prime}\times\{t_{0}\}\subset\mathcal{V}\times\mathcal{T} corresponds to restricting the signal to a vertex subset \mathcal{V}^{\prime} , and the operator \Pi_{\VT} reduces to the vertex-limiting operator \Pi_{\mathcal{V}^{\prime}} [ 16 ] . b) Time-limiting projection: For a trivial graph \mathcal{G} with a single vertex v_{0} , f\in L^{2}(\{v_{0}\}\times\mathcal{T})\cong L^{2}(\mathcal{T}) is a continuous-time signal on \mathcal{T}=\mathbb{R} . Let \mathcal{T}^{\prime}=[t_{c}-\ell/2,t_{c}+\ell/2] be an interval within \mathcal{T} , where t_{c} is the center time point and \ell is the length of \mathcal{T}^{\prime} . In this case, \mathcal{S}=\{v_{0}\}\times\mathcal{T}^{\prime} , and the operator \Pi_{\VT} reduces to the time-limiting operator \Pi_{\mathcal{T}^{\prime}} in [ 3 ] , which restricts the signal f(t)=f(v_{0},t) to \mathcal{T}^{\prime} . 2. Define \small\cal H_{\VT}=\overline{\mathrm{span}}\left\{\begin{aligned} &e^{-\tau_{v}\mathbf{L}}\delta_{v_{0}}\otimes\frac{1}{\sqrt{4\pi\tau_{t}}}\exp\!\Big(-\frac{(t-t_{0})^{2}}{4\tau_{t}}\Big)\\ &\qquad:\;v_{0}\in\mathcal{V}^{\prime},\;t_{0}\in\mathcal{T}^{\prime}\end{aligned}\right\}, where e^{-\tau_{v}\mathbf{L}}\delta_{v_{0}} is the graph heat atom centered at vertex v_{0} , and \frac{1}{\sqrt{4\pi\tau_{t}}}e^{-\frac{(t-t_{0})^{2}}{4\tau_{t}}} is the Gaussian heat kernel in the time domain centered at time t_{0} . The parameters \tau_{v}>0 and \tau_{t}>0 control the diffusion scales in the vertex and time domains, respectively, and allow one to model signals that are localized around specific vertices and time instances (cf. section III-C ). Definition 2 (Spectral-frequency projection) . Let \mathcal{U}:L^{2}(\mathcal{V}\times\mathcal{T})\rightarrow L^{2}(\Lambda\times\Omega) be the JFT in eq. 2 , and let \mathcal{H}_{\SF}\subseteq L^{2}(\Lambda\times\Omega) be a closed subspace. The spectral-frequency projection operator \Pi_{\SF} , for each vertex-time graph signal f\in L^{2}(\mathcal{V}\times\mathcal{T}) , is defined as follows: \displaystyle\Pi_{\SF}f=\mathcal{U}^{-1}\Sigma_{\SF}\{\mathcal{U}f\} (4) where \Sigma_{\SF} denotes the orthogonal projection onto \mathcal{H}_{\SF} . The operator \Pi_{\SF} is Hermitian and idempotent, i.e., \Pi_{\SF}^{2}=\Pi_{\SF} . In practice, one often takes \mathcal{H}_{\SF} to be the subspace of functions supported on a measurable spectral-frequency region \Sigma\subseteq\Lambda\times\Omega , namely \mathcal{H}_{\SF}=\left\{g\in L^{2}(\Lambda\times\Omega)\nonscript\,:\allowbreak\nonscript\,\mathopen{}g(\lambda,\omega)=0\ \text{for}\ (\lambda,\omega)\notin\Sigma\right\} for some measurable subset \Sigma\subseteq\Lambda\times\Omega . In this case, \Pi_{\SF} is the spectral-frequency limiting operator, 2 2 2 We omit \mathcal{U} in the notation \Pi_{\Sigma} to avoid clutter, which is clear from the context. defined by \displaystyle\Pi_{\SF}f=\Pi_{\Sigma}:=\mathcal{U}^{-1}\Sigma\{\mathcal{U}f\}, (5) where \displaystyle\Sigma\{\mathcal{U}f\}:=\begin{cases}(\mathcal{U}f)(\lambda,\omega)&\text{if }(\lambda,\omega)\in\Sigma,\\ 0&\text{otherwise},\end{cases} i.e., \Pi_{\SF} zeroes the JFT outside \Sigma to form a bandlimited signal. The operator \Pi_{\SF} recovers familiar special cases: 1. For signals f\in L^{2}(\mathcal{V}\times\{t_{0}\}) with f(v)=f(v,t_{0})\in\mathbb{C} for v\in\mathcal{V} , the transform \mathcal{U} can be the GFT in eq. 1 . Then \Pi_{\SF} becomes the spectral-limiting projector \Pi_{\Lambda^{\prime}}=\mathbf{U}\Sigma_{\Lambda^{\prime}}\mathbf{U}^{\ast} , where \Lambda^{\prime}\subset\Lambda and \Sigma_{\Lambda^{\prime}}=\diag(\mathbf{1}_{\Lambda^{\prime}}) , projecting f onto the subspace spanned by eigenvectors indexed by \Lambda^{\prime} [ 16 ] . 2. For a trivial graph consisting of a single vertex, \mathcal{U} can be the FT \mathcal{F} mapping L^{2}(\mathcal{T}) to L^{2}(\Omega) . For a frequency band \Omega^{\prime}=[\omega_{c}-W,\omega_{c}+W] , where \omega_{c} denotes the center frequency and W the bandwidth, \Pi_{\SF} reduces to the classical frequency-limiting operator \Pi_{\Omega^{\prime}} [ 3 , 4 ] , which produces the bandlimited function \displaystyle\Pi_{\Omega^{\prime}}f(t)=\frac{1}{2\pi}\int_{\omega_{c}-W}^{\omega_{c}+W}\mathcal{F}_{f}(\omega)\,e^{\mathfrak{i}\mkern 1.0mu\omega t}\,\mathrm{d}\omega. Let \mathcal{H}_{\VT}\subseteq L^{2}(\mathcal{V}\times\mathcal{T}) be a closed subspace, with \mathcal{H}_{\VT}^{\perp} denoting its orthogonal complement, and let \overline{\Pi}_{\VT} denote the orthogonal projection onto \mathcal{H}_{\VT}^{\perp} . Then \overline{\Pi}_{\VT}=\mathcal{I}-\Pi_{\VT} , where \mathcal{I} is the identity on L^{2}(\mathcal{V}\times\mathcal{T}) . In particular \overline{\Pi}_{\VT} is self - adjoint and idempotent, i.e., \overline{\Pi}_{\VT}^{\ast}=\overline{\Pi}_{\VT} and \overline{\Pi}_{\VT}^{2}=\overline{\Pi}_{\VT} . The same relations hold for the spectral–frequency projector: \overline{\Pi}_{\SF}=\mathcal{I}-\Pi_{\SF} and \Pi_{\SF}+\overline{\Pi}_{\SF}=\mathcal{I} . Definition 3 (Vertex-time spread and spectral-frequency spread) . Given the vertex-time projection operator \Pi_{\VT} and the spectral-frequency projection operator \Pi_{\SF} , the vertex-time spread and spectral-frequency spread of a vertex-time graph signal f\in L^{2}(\mathcal{V}\times\mathcal{T}) are defined with respect to these subspaces as follows: \displaystyle\alpha^{2}_{\VT}=\frac{\lVert\Pi_{\VT}f\rVert_{\mathcal{H}_{\VT}}^{2}}{\lVert f\rVert_{L^{2}(\cal{V}\times\cal{T})}^{2}}~~\text{and}~~\beta^{2}_{\SF}=\frac{\lVert\Pi_{\SF}f\rVert_{\mathcal{H}_{\SF}}^{2}}{\lVert f\rVert_{L^{2}(\cal{V}\times\cal{T})}^{2}}. (6) These quantities measure the fractions of signal energy contained in the vertex–time and spectral–frequency subspaces, respectively. II-C Uncertainty principle for vertex-time graph signals Given a closed vertex-time subspace \mathcal{H}_{\VT} and a spectral-frequency subspace \mathcal{H}_{\SF} , the uncertainty principle for vertex-time graph signals establishes a trade-off between \alpha_{\VT}^{2} and \beta_{\SF}^{2} , as stated in the following theorem. Theorem 1 . For a given \mathcal{H}_{\VT} and \mathcal{H}_{\SF} , the feasible region \Theta of achievable pairs (\alpha_{\VT},\beta_{\SF}) is given by \displaystyle\begin{aligned} &\Theta=\Bigg\{(\alpha_{\VT},\beta_{\SF}):\\ &\cos^{-1}\alpha_{\VT}+\cos^{-1}\beta_{\SF}\geq\cos^{-1}\sqrt{\lambda_{\max}(\Pi_{\SF}\Pi_{\VT}\Pi_{\SF})},\\ &\cos^{-1}\sqrt{1-\alpha_{\VT}^{2}}+\cos^{-1}\beta_{\SF}\geq\cos^{-1}\sqrt{\lambda_{\max}(\Pi_{\SF}\overline{\Pi}_{\VT}\Pi_{\SF})},\\ &\cos^{-1}\alpha_{\VT}+\cos^{-1}\sqrt{1-\beta_{\SF}^{2}}\geq\cos^{-1}\sqrt{\lambda_{\max}(\overline{\Pi}_{\SF}\Pi_{\VT}\overline{\Pi}_{\SF})}\\ &\cos^{-1}\sqrt{1-\alpha_{\VT}^{2}}+\cos^{-1}\sqrt{1-\beta_{\SF}^{2}}\\ &\qquad\qquad\qquad\geq\cos^{-1}\sqrt{\lambda_{\max}(\overline{\Pi}_{\SF}\overline{\Pi}_{\VT}\overline{\Pi}_{\SF})}\Bigg\}\end{aligned} (7) where \lambda_{\max}(\cdot) denotes the largest eigenvalue of its operator argument. I.e., there exists a f\in L^{2}(\mathcal{V}\times\mathcal{T}) with \lVert\Pi_{\VT}f\rVert=\alpha_{\VT} and \lVert\Pi_{\SF}f\rVert=\beta_{\SF} if and only if (\alpha_{\VT},\beta_{\SF})\in\Theta . Proof: The proof follows the same steps as the corresponding proof in [ 16 ] and is provided for completeness in the Appendices. ∎ \alpha_{\VT}^{2} \beta_{\SF}^{2} \lambda_{\max}(\overline{\Pi}_{\VT}\Pi_{\SF}\overline{\Pi}_{\VT}) 1\!\!-\!\!\lambda_{\max}(\overline{\Pi}_{\VT}\overline{\Pi}_{\SF}\overline{\Pi}_{\VT}) 1\!\!-\!\!\lambda_{\max}(\overline{\Pi}_{\SF}\overline{\Pi}_{\VT}\overline{\Pi}_{\SF}) \lambda_{\max}(\overline{\Pi}_{\SF}\Pi_{\VT}\overline{\Pi}_{\SF}) 1\!\!-\!\!\lambda_{\max}(\Pi_{\SF}\overline{\Pi}_{\VT}\Pi_{\SF}) \lambda_{\max}(\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}) \lambda_{\max}(\Pi_{\VT}\Pi_{\SF}\Pi_{\VT}) 1\!\!-\!\!\lambda_{\max}(\Pi_{\VT}\overline{\Pi}_{\SF}\Pi_{\VT}) 1 1 Fig. 2 : Feasible region \Theta of \alpha_{\VT} and \beta_{\SF} Figure 2 depicts the feasible region \Theta . The four boundary curves arise by turning the inequalities in eq. 7 into equalities; these curves form the four corner arcs shown in the figure. In particular, the upper - right boundary identifies pairs (\alpha_{\VT},\beta_{\SF}) that achieve the largest possible joint concentration in the vertex–time and spectral–frequency domains. This boundary is characterized by the equality \cos^{-1}\alpha_{\VT}+\cos^{-1}\beta_{\SF}=\cos^{-1}\sqrt{\lambda_{\max}\left(\Pi_{\SF}\,\Pi_{\VT}\,\Pi_{\SF}\right)} . Typically, for a fixed spectral–frequency subspace \mathcal{H}_{\SF} , enlarging the vertex–time subspace \mathcal{H}_{\VT} expands the feasible region and moves its upper - right boundary toward the upper - right corner. Here, enlarging a subspace is defined through strict inclusion, i.e., replacing \mathcal{H}_{\VT} with a larger subspace \mathcal{H}_{\VT}^{{}^{\prime}} satisfying \mathcal{H}_{\VT}\subsetneq\mathcal{H}_{\VT}^{{}^{\prime}} . The boundary curve collapses to that corner precisely when the projectors \Pi_{\VT} and \Pi_{\SF} admit perfect localization (see section III-A ). Note that, under our subspace formulation, both \mathcal{H}_{\SF} and \mathcal{H}_{\VT} may have infinite dimension. More generally, any of the four boundary arcs in fig. 2 can collapse to its corresponding corner whenever the associated projector composition satisfies the perfect - localization condition. Finally, it is instructive to compare the joint feasible region in eq. 7 with the analogous regions that arise when only the vertex domain or only the time domain is considered. II-D Special case of vertex-time and spectral-frequency subsets with product structure In the special case of eq. 3 and eq. 5 , if the vertex-time subset \mathcal{S} has a product structure, then the vertex-time spread is bounded by the product of the vertex spread and time spread. A similar bound holds for the spectral-frequency spread. Lemma 1 . Given \mathcal{S}=\mathcal{V}^{\prime}\times\mathcal{T}^{\prime}\subseteq\mathcal{V}\times\mathcal{T} and \Sigma=\Lambda^{\prime}\times\Omega^{\prime}\subseteq\Lambda\times\Omega , let the vertex spread at a time t and the time spread at a vertex v be \displaystyle\alpha^{2}_{\mathcal{V}^{\prime}}(t)=\frac{\lVert f(\cdot,t)\rVert_{L^{2}(\mathcal{V}^{\prime})}^{2}}{\lVert f(\cdot,t)\rVert_{L^{2}(\mathcal{V})}^{2}}~\text{and}~\alpha^{2}_{\mathcal{T}^{\prime}}(v)=\frac{\lVert f(v,\cdot)\rVert_{L^{2}(\mathcal{T}^{\prime})}^{2}}{\lVert f(v,\cdot)\rVert_{L^{2}(\mathcal{T})}^{2}} (8) respectively. Let the spectral spread at a (time) frequency \omega and the frequency spread at a (graph) spectrum \lambda be \displaystyle\beta^{2}_{\Lambda^{\prime}}(\omega)=\frac{\lVert\mathcal{U}f(\cdot,\omega)\rVert_{L^{2}(\Lambda^{\prime})}^{2}}{\lVert\mathcal{U}f(\cdot,\omega)\rVert_{L^{2}(\Lambda)}^{2}}~\text{and}~\beta^{2}_{\Omega^{\prime}}(\lambda)=\frac{\lVert\mathcal{U}f(\lambda,\cdot)\rVert_{L^{2}(\Omega^{\prime})}^{2}}{\lVert\mathcal{U}f(\lambda,\cdot)\rVert_{L^{2}(\Omega)}^{2}} (9) respectively. The vertex-time spread \alpha_{\mathcal{S}}^{2} and spectral-frequency spread \beta_{\Sigma}^{2} are bounded as follows: \displaystyle\min_{v}\alpha^{2}_{\mathcal{T}^{\prime}}(v)\inf_{t}\alpha^{2}_{\mathcal{V}^{\prime}}(t)\leq\alpha^{2}_{\mathcal{S}}\leq\max_{v}\alpha^{2}_{\mathcal{T}^{\prime}}(v)\sup_{t}\alpha^{2}_{\mathcal{V}^{\prime}}(t) (10) and \displaystyle\min_{\lambda}\beta^{2}_{\Omega^{\prime}}(\lambda)\inf_{\omega}\beta_{\Lambda^{\prime}}^{2}(\omega)\leq\beta^{2}_{\Sigma}\leq\max_{\lambda}\beta^{2}_{\Omega^{\prime}}(\lambda)\sup_{\omega}\beta_{\Lambda^{\prime}}^{2}(\omega). (11) Proof: See appendix B . ∎ We assume that the supremum and infimum in 1 are achievable, and use the notations \alpha_{\mathcal{T}^{\prime}}^{\text{min}} , \alpha^{\text{min}}_{\mathcal{V}^{\prime}} , \alpha_{\mathcal{T}^{\prime}}^{\text{max}} , and \alpha_{\mathcal{V}^{\prime}}^{\text{max}} as abbreviations for \min_{v}\alpha_{\mathcal{T}^{\prime}}(v) , \inf_{t}\alpha_{\mathcal{V}^{\prime}}(t) , \max_{v}\alpha_{\mathcal{T}^{\prime}}(v) and \sup_{t}\alpha_{\mathcal{V}^{\prime}}(t) , respectively. Similarly, we define \beta_{\Lambda^{\prime}}^{\text{min}} , \beta^{\text{min}}_{\Omega^{\prime}} , \beta_{\Lambda^{\prime}}^{\text{max}} , and \beta_{\Omega^{\prime}}^{\text{max}} as \inf_{\omega}\beta_{\Lambda^{\prime}}(\omega) , \min_{\lambda}\beta_{\Omega^{\prime}}(\lambda) , \sup_{\omega}\beta_{\Lambda^{\prime}}(\omega) , and \max_{\lambda}\beta_{\Omega^{\prime}}(\lambda) , respectively. Theorem 2 . Consider a special case \Pi_{\VT}=\Pi_{\mathcal{S}} and \Pi_{\SF}=\Pi_{\Sigma} and such two subsets \mathcal{S}=\mathcal{V}^{\prime}\times\mathcal{T}^{\prime}\subseteq\mathcal{V}\times\mathcal{T} and \Sigma=\Lambda^{\prime}\times\Omega^{\prime}\subseteq\Lambda\times\Omega . Suppose (\alpha_{\mathcal{S}},\beta_{\Sigma})\in\Theta . Given the spectral spread \beta^{2}_{\Lambda^{\prime}} and the frequency spread \beta^{2}_{\Omega^{\prime}} , defined in eq. 9 , the feasible region \Theta_{\alpha_{\mathcal{S}}} of \alpha_{\mathcal{S}} is given by \displaystyle\alpha_{\mathcal{S}}\leq\cos\Big(\cos^{-1}\sqrt{\lambda_{\max}\left(\Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}}\right)\lambda_{\max}\left(\Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}}\right)} \displaystyle\qquad\qquad\qquad-\cos^{-1}\left(\beta_{\Lambda^{\prime}}^{\min}\beta_{\Omega^{\prime}}^{\min}\right)\Big) (12a) \displaystyle\alpha_{\mathcal{S}}\leq\cos\Big(\cos^{-1}\sqrt{\lambda_{\max}\left(\overline{\Pi}_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\overline{\Pi}_{\Lambda^{\prime}}\right)\lambda_{\max}\left(\overline{\Pi}_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\overline{\Pi}_{\Omega^{\prime}}\right)} \displaystyle\qquad\qquad\qquad-\cos^{-1}\Big(\sqrt{1-(\beta_{\Lambda^{\prime}}^{\max}\beta^{\max}_{\Omega^{\prime}})^{2}}\Big)\Big), (12b) \displaystyle\alpha_{\mathcal{S}}\geq\sin\Big(\cos^{-1}\sqrt{\lambda_{\max}\left(\Pi_{\Lambda^{\prime}}\overline{\Pi}_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}}\right)\lambda_{\max}\left(\Pi_{\Omega^{\prime}}\overline{\Pi}_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}}\right)} \displaystyle\qquad\qquad\qquad-\cos^{-1}\left(\beta_{\Lambda^{\prime}}^{\min}\beta_{\Omega^{\prime}}^{\min}\right)\Big), (12c) \displaystyle\alpha_{\mathcal{S}}\geq\sin\Big(\cos^{-1}\sqrt{\lambda_{\max}\left(\overline{\Pi}_{\Lambda^{\prime}}\overline{\Pi}_{\mathcal{V}^{\prime}}\overline{\Pi}_{\Lambda^{\prime}}\right)\lambda_{\max}\left(\overline{\Pi}_{\Omega^{\prime}}\overline{\Pi}_{\mathcal{T}^{\prime}}\overline{\Pi}_{\Omega^{\prime}}\right)} \displaystyle\qquad\qquad\qquad-\cos^{-1}\Big(\sqrt{1-\left(\beta_{\Lambda^{\prime}}^{\max}\beta^{\max}_{\Omega^{\prime}}\right)^{2}}\Big)\Big) (12d) where \lambda_{\max}(\cdot) denotes the largest eigenvalue of its operator argument. Proof: See appendix C . ∎ 2 generalizes [ 16 ] by extending vertex-domain localization to vertex–time localization, and it bounds the vertex–time spread \alpha_{\mathcal{S}} in terms of the spectral spread \beta_{\Lambda^{\prime}} and the frequency spread \beta_{\Omega^{\prime}} . Although similar spread bounds can be formulated in a discrete-time setting, the continuous-time formulation offers greater flexibility: it permits localization over arbitrary measurable time intervals , whereas discrete time only allows localization over subsets of a fixed sampling grid common to all nodes. For cases of interest, where we assume that observations at different nodes are not synchronized, creating a common sampling grid across nodes would require selecting arbitrarily small sampling intervals or introducing some temporal distortion if the timing of some observations does not match sampling times. In contrast, the continuous-time setting allows localization over arbitrary measurable intervals, yielding resolution-independent projection operators and enabling the rigorous derivation of the spread bound in eq. 12a . In particular, the upper bound in eq. 12a provides a theoretical criterion for selecting the subset \mathcal{S} with maximal energy concentration. The selected subset \mathcal{S} is then used to design energy-concentrated bases, which are applied to discrete observations for signal reconstruction. Moreover, by combining the range of the vertex-time spread \alpha^{2}_{\mathcal{S}} , as given in eq. 10 , we have \displaystyle\begin{aligned} \small&\beta_{\Sigma}\leq\cos\Big(\cos^{-1}\sqrt{\lambda_{\max}\left(\Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}}\right)\lambda_{\max}\left(\Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}}\right)}\\ &\qquad\qquad-\cos^{-1}\left(\alpha_{\mathcal{V}^{\prime}}^{\min}\alpha_{\mathcal{T}^{\prime}}^{\min}\right)\Big).\end{aligned} (13) While time-frequency localization is well understood, vertex-spectral localization can exhibit different behaviors depending on the graph structure, which may affect the tightness of the bound; nevertheless, it still provides a principled and informative criterion for graph topology inference, allowing us to promote energy concentration in the spectral-frequency domain. III Vertex-time graph signal reconstruction Based on the vertex-time uncertainty principle, we propose a dictionary of signals that exhibit maximal energy concentration in the vertex-time domain. We characterize the localization properties of these signals and establish conditions for perfect localization within prescribed closed subspaces defined on the vertex-time and spectral-frequency domains. We then present methods for constructing and optimizing these atoms. III-A Localization properties A vertex-time signal f\in L^{2}(\mathcal{V}\times\mathcal{T}) is said to be perfectly localized in the closed vertex-time subspace \mathcal{H}_{\VT} if \displaystyle\Pi_{\VT}f=f, (14) where \Pi_{\VT} is the orthogonal projection onto \mathcal{H}_{\VT} (cf. 1 ). Similarly, f is perfectly localized in the spectral–frequency subspace \mathcal{H}_{\SF} if \displaystyle\Pi_{\SF}f=f, (15) with \Pi_{\SF} the spectral–frequency projector from 2 . In practice, \mathcal{H}_{\SF} is often a support - limited subspace, i.e., functions whose joint spectral–frequency content is confined to a measurable region \Sigma\subseteq\Lambda\times\Omega ; signals satisfying ( 15 ) are also referred to as joint bandlimited signals. Under our definition, a vertex-time graph signal can achieve perfect localization simultaneously in the vertex-time and spectral-frequency domains with suitable choices of \mathcal{H}_{\VT} and \mathcal{H}_{\SF} . This dual localization property is formalized in the following theorem. Theorem 3 . A vertex-time graph signal f is perfectly localized over both the vertex-time subspace \mathcal{H}_{\VT} and spectral-frequency subspace \mathcal{H}_{\SF} (i.e., f\in\ima(\Pi_{\VT})\cap\ima(\Pi_{\SF}) ) if and only if the Hermitian operator \Pi_{\SF}\Pi_{\VT}\Pi_{\SF} (or equivalently, \Pi_{\VT}\Pi_{\SF}\Pi_{\VT} ) satisfies \displaystyle\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}f=f. (16) An equivalent condition is \displaystyle\lVert\Pi_{\VT}\Pi_{\SF}\rVert=\lVert\Pi_{\SF}\Pi_{\VT}\rVert=1, (17) where \lVert\cdot\rVert is the operator norm corresponding to L^{2}(\mathcal{V}\times\mathcal{T}) . Proof: See appendix D . ∎ To illustrate 3 , consider the following special cases: 1. In the case where f\in L^{2}(\mathcal{V}) (traditional GSP), a perfectly localized f is an eigenvector of the operator \Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\Pi_{\mathcal{W}^{\prime}} associated with a unit eigenvalue, aligning with [ 16 , Theorem 2.1] . 2. When the graph \mathcal{G} consists of a single vertex, the limiting operators \Pi_{\SF} and \Pi_{\VT} reduce to the frequency-limiting operator \Pi_{\Omega^{\prime}} and the time-limiting operator \Pi_{\mathcal{T}^{\prime}} . If \mathcal{T}^{\prime}\subset\mathbb{R} and \Omega^{\prime}=[-W,W]\subset\mathbb{R} are both bounded sets, the condition in eq. 16 no longer holds because the largest eigenvalue \lambda_{\max}(\Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}}) is strictly less than 1 (see [ 4 ] ). This result illustrates the classical time-frequency uncertainty principle: no nonzero signal can simultaneously have both a finite time duration and a finite frequency bandwidth. 3. Consider two subsets \mathcal{S}=\mathcal{V}^{\prime}\times\mathcal{T}^{\prime}\subseteq\mathcal{V}\times\mathcal{T} and \Sigma=\Lambda^{\prime}\times\Omega^{\prime}\subseteq\Lambda\times\Omega , where \mathcal{T}^{\prime}\subset\mathbb{R} and \Omega^{\prime}\subset\mathbb{R} are both bounded sets. The vertex-time limiting operator \Pi_{\mathcal{S}} and the spectral-frequency limiting operator \Pi_{\Sigma} decompose as \Pi_{\mathcal{S}}=\Pi_{\mathcal{V}^{\prime}}\otimes\Pi_{\mathcal{T}^{\prime}} and \Pi_{\Sigma}=\Pi_{\Lambda^{\prime}}\otimes\Pi_{\Omega^{\prime}} , respectively. Then \Pi_{\Sigma}\Pi_{\mathcal{S}}\Pi_{\Sigma}=\left(\Pi_{\Lambda^{\prime}}\otimes\Pi_{\Omega^{\prime}}\right)\left(\Pi_{\mathcal{V}^{\prime}}\otimes\Pi_{\mathcal{T}^{\prime}}\right)\left(\Pi_{\Lambda^{\prime}}\otimes\Pi_{\Omega^{\prime}}\right) and its largest eigenvalue factors as \displaystyle\lambda_{\max}(\Pi_{\Sigma}\Pi_{\mathcal{S}}\Pi_{\Sigma})=\lambda_{\max}(\Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}})\lambda_{\max}(\Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}}), which is less than 1 as \lambda_{\max}(\Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}})<1 . Consequently, a vertex-time graph signal f cannot be perfectly localized over both the vertex-time subset \mathcal{S} and the spectral-frequency subset \Sigma simultaneously. When perfect localization in both \mathcal{H}_{\VT} and \mathcal{H}_{\SF} is not achievable, we seek signals that are perfectly localized in one domain while maximizing energy concentration in the other. A common instance is to construct an orthonormal family of bandlimited functions (i.e., satisfying \Pi_{\Sigma}f=f in eq. 5 ) that are as concentrated as possible in the vertex–time subspace \mathcal{H}_{\VT} . This is obtained by solving the following sequence of constrained optimization problems for \{\xi_{i}\}_{i\geq 1} : \displaystyle\begin{aligned} \xi_{i}=&\argmax_{\xi_{i}}\lVert\Pi_{\VT}\xi_{i}\rVert\\ \ST&\lVert\xi_{i}\rVert=1,\ \Pi_{\Sigma}\xi_{i}=\xi_{i},\\ &\langle\xi_{i},\xi_{j}\rangle=0,\;j=1,\dots,i-1,\;i>1.\end{aligned} (18) Accordingly, \xi_{1} is the bandlimited function with the largest \mathcal{H}_{\VT} energy, \xi_{2} is the next bandlimited function orthogonal to \xi_{1} with maximal \mathcal{H}_{\VT} energy, and so on. The next theorem characterizes the solution to eq. 18 . Theorem 4 . A set of orthonormal joint bandlimited signals \{\xi_{i}\}_{i\geq 1} , each of which is maximally concentrated over a vertex-time subspace \mathcal{H}_{\VT} , consists of the eigenvectors of the operator \Pi_{\Sigma}\Pi_{\VT}\Pi_{\Sigma} , i.e., \displaystyle\Pi_{\Sigma}\Pi_{\VT}\Pi_{\Sigma}\xi_{i}=\lambda_{i}\xi_{i}, (19) where the eigenvalues \lambda_{1}\geq\lambda_{2}\geq\cdots form a non-increasing sequence whose only possible limit is zero. Additionally, for all i,j\geq 1 , \displaystyle\langle\xi_{i},\Pi_{\VT}\xi_{j}\rangle=\lambda_{j}\delta_{ij}, (20) where \delta_{ij} is the Kronecker symbol. Proof: See appendix E . ∎ 4 provides a general framework for constructing a set of orthonormal bandlimited signals \{\xi_{i}\}_{i=1,2,\dots} where \xi_{i}\in L^{2}(\mathcal{V}\times\mathcal{T}) . Specific cases include: 1. In traditional GSP, the set of orthonormal bandlimited signals corresponds to the set of orthonormal eigenvectors of \Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}} , as stated in [ 16 , Theorem 2.3] . 2. Suppose the graph \mathcal{G} consists of a single vertex and the limiting projection \Pi_{\mathcal{S}} reduces to the time-limiting operator \Pi_{\mathcal{T}^{\prime}} . The orthonormal joint bandlimited signals are then the prolate spheroidal wave functions \{\psi_{i}\}_{i\geq 1} [ 3 , 5 , 4 ] , achieved by the eigenfunctions of \Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}} defined in the Hilbert space L^{2}(\mathbb{R}) . 3. Consider the subsets \mathcal{S}=\mathcal{V}^{\prime}\times\mathcal{T}^{\prime}\subseteq\mathcal{V}\times\mathcal{T} and \Sigma=\Lambda^{\prime}\times\Omega^{\prime}\subseteq\Lambda\times\Omega . The vertex-time limiting operator \Pi_{\mathcal{S}} and the spectral-frequency limiting operator \Pi_{\Sigma} can be expressed as \Pi_{\mathcal{S}}=\Pi_{\mathcal{V}^{\prime}}\otimes\Pi_{\mathcal{T}^{\prime}} and \Pi_{\Sigma}=\Pi_{\Lambda^{\prime}}\otimes\Pi_{\Omega^{\prime}} , respectively. The set of orthonormal joint bandlimited signals is given by \{\xi_{i,j}\}_{i,j\geq 1}=\{\phi_{i}\otimes\psi_{j}\}_{i,j\geq 1} . Here, \{\phi_{i}\}_{i\geq 1} are the orthonormal bandlimited vectors given by the eigenvectors of \Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}} in the vertex domain, and \{\psi_{j}\}_{j\geq 1} are the orthonormal bandlimited signals (prolate spheroidal wave functions), determined by the eigenfunctions of \Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}} defined in the Hilbert space L^{2}(\mathbb{R}) . For numerical implementation, we parametrize the vertex–time subspace \mathcal{H}_{\VT} . We study two representative parameterizations: (i) a support - limited subspace (see section III-B ), and (ii) a Gaussian heat - kernel subspace (See section III-C ). Both constructions yield joint bandlimited functions that are highly concentrated in the vertex–time domain, and their parameters are chosen to improve reconstruction accuracy. In the support - limited case, we assemble a dictionary of joint bandlimited atoms supported on selected vertex–time blocks and employ a dictionary - learning procedure to select the most informative atoms. In the Gaussian case, we grid-search the spatial and temporal diffusion scales and choose the pair that maximizes a predefined concentration score; then, we reconstruct by projecting onto the resulting basis. III-B Joint parametric dictionary learning with support-limited subspace for vertex-time signal reconstruction An overcomplete dictionary can enhance signal reconstruction by enabling sparse, flexible, and robust signal representations. Motivated by sensor networks in which different sensors may be active or provide measurements over distinct, possibly non-overlapping time periods, empirical observations indicate that signal energy is not uniformly distributed across vertices or over time. Instead, it tends to concentrate in a limited region of the vertex–time domain (cf. fig. 1 ). To capture this localized structure while maintaining computational feasibility, we consider a structured low-dimensional parametric family of atoms with a vertex–time support of the form \mathcal{S}=\mathcal{V}^{\prime}\times\mathcal{T}^{\prime} , where \mathcal{T}^{\prime}=[t_{c}-\ell/2,t_{c}+\ell/2] denotes a finite time interval centered at t_{c} with duration \ell , and \mathcal{V}^{\prime}\subseteq\mathcal{V} is a vertex subset designed to capture the dominant energy localization behavior over \mathcal{T}^{\prime} . Under this model, atoms are not learned as free vectors; rather, they are generated analytically from parameters (\mathcal{V}^{\prime},t_{c},\ell) , so learning reduces to selecting \mathcal{V}^{\prime} and (t_{c},\ell) that best match the observed energy localization. This parameterization explicitly encodes where energy is expected to concentrate in the vertex–time plane, yielding energy-concentrated atoms for efficient reconstruction. Our objective is to learn a dictionary bandlimited to \Sigma=\Lambda^{\prime}\times\Omega^{\prime} and maximally concentrated on \mathcal{S} . Let \Phi(\mathcal{V}^{\prime})=\left(\phi_{k}(\cdot;\mathcal{V}^{\prime}\right)_{k\geq 1} , where for each k\geq 1 , \phi_{k}(\cdot;\mathcal{V}^{\prime}):\mathcal{V}\rightarrow\mathbb{R} is an eigenvector of \Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}} , which is a graph signal localized over \mathcal{V}^{\prime} . Let \Psi(\mathcal{T}^{\prime})=\left(\psi_{n}(\cdot;\mathcal{T}^{\prime}\right)_{n\geq 1} , where for each n\geq 1 , \psi_{n}(\cdot;\mathcal{T}^{\prime}):\mathcal{T}\rightarrow\mathbb{R} is a PSWF localized over \mathcal{T}^{\prime} . Each \psi_{n}(\cdot;\mathcal{T}^{\prime}) is an eigenfunction of \Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}} . We construct a dictionary candidate as \displaystyle\Xi(\mathcal{V}^{\prime},\mathbf{t}_{c},{\bm{\ell}})=\Phi(\mathcal{V}^{\prime})\otimes\Psi(\mathcal{T}^{\prime}), (21) where \displaystyle\Phi(\mathcal{V}^{\prime})\otimes\Psi(\mathcal{T}^{\prime})=\left(\phi_{k}(\cdot;{\mathcal{V}^{\prime}})\otimes\psi_{n}(\cdot;{\mathcal{T}^{\prime}})\right)_{k,n\geq 1} is the set of signals localized over \mathcal{S} . While dictionaries with analytical forms and predefined parameters capture global signal structure for reconstruction, learned dictionaries with optimized parameters outperform by adapting to observed signals [ 36 , 37 , 38 ] . Our goal is to optimize these parameters \mathcal{V}^{\prime} , t_{c} and \ell to construct an energy-concentrated vertex–time dictionary that enables accurate and efficient signal reconstruction using training samples. We adopt a train-test protocol: the dictionary parameters (\mathcal{V}^{\prime},t_{c},\ell) are learned from the training samples, and the resulting dictionary is then fixed and used to reconstruct held-out testing signals. We assume the training and testing data are generated by the same underlying process, so that they share similar vertex–time energy localization patterns and consistent spectral/frequency characteristics induced by the same graph topology and bandwidth-related priors. Let \mathcal{M}_{\mathrm{train}}=\{(v_{m},t_{m})\nonscript\,:\allowbreak\nonscript\,\mathopen{}m=1,\dots,M\} be the discrete vertex-time instants at which the noisy observations y_{m}=f(v_{m},t_{m})+\epsilon_{m} , m=1,\dots,M are available, where \epsilon_{m} are independent and identically distributed (i.i.d.) zero-mean random variables with variance \sigma^{2} . Let the training samples be denoted by \mathbf{Y}_{\mathrm{train}}=\bigl(y_{m}\bigr)_{m=1,\dots,M} . We consider a general (possibly irregular) sampling model in which each (v_{m},t_{m}) corresponds to a single measurement event, and the index m enumerates samples rather than time instants. In particular, \mathcal{M}_{\mathrm{train}} may be generated by a random sampling mechanism, so observations may occur at arbitrary vertex-time pairs and need not be synchronized across vertices. We assume the signal of interest is localized within a finite interval [0,\delta] . The dictionary \Xi(\mathcal{V}^{\prime},t_{c},\ell) consists of vertex-time dictionary atoms(columns), i.e., continuous time functions defined on \mathcal{V}\times[0,\delta] , whose energy is concentrated on \mathcal{V}^{\prime}\times\mathcal{T}^{\prime} , where \mathcal{T}^{\prime}=[t_{c}-\ell/2,\,t_{c}+\ell/2] and \mathcal{V}^{\prime}\subseteq\mathcal{V} . Evaluating these atoms at the training instances \mathcal{M}_{\mathrm{train}} yields a finite dictionary matrix, denoted by \Xi(\mathcal{M}_{\mathrm{train}};\mathcal{V}^{\prime},t_{c},\ell) , where each column corresponds to one of the atoms. The dictionary learning problem is as follows: Problem 1 (Joint Energy Concentrated Dictionary Learning) . Given the training measurement set \mathcal{M}_{\mathrm{train}} , and the noisy observations \mathbf{Y}_{\mathrm{train}} , the goal is to learn the energy-concentrated vertex–time dictionary (i.e., supported by eq. 12a in 2 ) by jointly estimating the sparse coefficients \mathbf{x} and the dictionary parameters (\mathcal{V}^{\prime},t_{c},\ell) . This leads to the following optimization problem: \displaystyle\begin{aligned} \argmin_{\mathbf{x},\mathcal{V}^{\prime},t_{c},\ell}\ &\lVert\mathbf{Y}_{\mathrm{train}}-\Xi(\mathcal{M}_{\mathrm{train}};\mathcal{V}^{\prime},t_{c},\ell)\mathbf{x}\rVert_{2}^{2}+\mu\lVert\mathbf{x}\rVert_{1}\\ \ST\ &t_{c}\in[0,\delta],\ 0\leq\ell\leq\delta\\ &\mathcal{V}^{\prime}~\text{is optimized in}~\lx@cref{creftype\lx@tilde refnum}{eq:ThetaS-1a}~\text{with}~\lvert\mathcal{V}^{\prime}\rvert\leq K\\ &\text{and}~K=\rank(\Pi_{\Lambda^{\prime}}).\end{aligned} (22) Here, both the spectral support \Lambda^{\prime} and the frequency support \Omega^{\prime} (implicitly included in eq. 12a ) are treated as prior knowledge and are estimated from the full data observations \mathbf{Y} via a cumulative-energy criterion. Specifically, we select the smallest set of graph and temporal frequencies whose cumulative energy accounts for at least a prescribed fraction \beta_{\Lambda^{\prime}} and \beta_{\Omega^{\prime}}\in(0,1] of the total signal energy respectively, i.e., \Lambda^{\prime}\in\argmin_{\Gamma\subseteq\Lambda}\lvert\Gamma\rvert,\ST\frac{\sum_{\lambda\in\Gamma}\lVert\Pi_{\lambda}\mathbf{Y}\rVert_{2}^{2}}{\lVert\mathbf{Y}\rVert_{2}^{2}}\geq\beta_{\Lambda^{\prime}}, and \Omega^{\prime}\in\argmin_{\Gamma\subseteq\Omega}\text{meas}(\Gamma),\ST\frac{\int_{\Gamma}\|\Pi_{\omega}\mathbf{Y}\|_{2}^{2}\,\mathrm{d}\omega}{\int_{\Omega}\|\Pi_{\omega}\mathbf{Y}\|_{2}^{2}\,\mathrm{d}\omega}\geq\beta_{\Omega^{\prime}} , where \text{meas}(\Gamma) denotes the Lebesgue measure of \Gamma . The \ell_{1} regularization term leads to sparse coefficients \mathbf{x} , while \mu controls the strength of the regularization. Although 1 captures the ideal objective of jointly optimizing the vertex subset \mathcal{V}^{\prime} , the dictionary parameters (t_{c},\ell) , and the sparse coefficients \mathbf{x} , it is highly nonconvex and combinatorial. In particular, the discrete optimization over \mathcal{V}^{\prime} is tightly coupled with the continuous dictionary parameters (t_{c},\ell) , making the problem intractable to solve globally. To obtain a computationally feasible solution, we decompose 1 into two subproblems: (i) vertex subset selection (See section III-B1 ), and (ii) dictionary learning via sparse coding with a fixed vertex subset \mathcal{V}^{\prime} , where the continuous dictionary parameters (t_{c},\ell) are optimized (See Section III-B2 ). This decomposition decouples the discrete subset selection from continuous parameter optimization, yielding a principled yet heuristic approximation to the joint objective. III-B 1 Vertex subset selection An effective dictionary design requires each atom to concentrate its energy on a carefully selected subset of vertices, while still preserving sufficient spectral coverage to capture the underlying graph structure. This balance between vertex-domain localization and spectral-domain expressiveness is essential for achieving accurate reconstruction using a compact and informative dictionary. To this end, we select vertex subsets \mathcal{V}^{\prime} to balance vertex localization and spectral coverage, ensuring that the spectral component continues to capture the underlying graph information while enabling accurate reconstruction with fewer, more informative atoms. Motivated by the upper bound of the feasible region in 2 , which characterizes the (\alpha_{\mathcal{S}},\beta_{\Sigma}) pairs achieving maximum localization in both vertex and spectral domains, the subset \mathcal{V}^{\prime} selection is posed as an energy-concentration maximization problem, shown in 1(a) . Problem 1(a) (Vertex Subset Selection for Energy-Concentrated Dictionary Design) . Given the spectral spread \beta_{\Lambda^{\prime}} , the frequency spread \beta_{\Omega^{\prime}} , a time interval \mathcal{T}^{\prime} , and a bandwidth constraint K=\rank(\Pi_{\Lambda^{\prime}}) , the goal is to select a vertex subset \mathcal{V}^{\prime} such that the resulting dictionary atoms are well localized in the vertex domain (i.e., maximizing energy concentration over vertex subset \mathcal{V}^{\prime} ) while maintaining sufficient spectral coverage. This leads to the following vertex selection problem: \displaystyle\begin{aligned} \argmax_{\mathcal{V}^{\prime}}\ &\cos\Big(\cos^{-1}\sqrt{\lambda_{\max}\left(\Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}}\right)\lambda_{\max}\left(\Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}}\right)}\\ &-\cos^{-1}\left(\beta_{\Lambda^{\prime}}\beta_{\Omega^{\prime}}\right)\Big)\\ \ST\ &\lvert\mathcal{V}^{\prime}\rvert\leq K,\ K=\rank(\Pi_{\Lambda^{\prime}}).\end{aligned} Algorithm 1 Greedy selection based on energy concentration maximization 1: Input: Spectral spread \beta_{\Lambda^{\prime}} , frequency spread \beta_{\Omega^{\prime}} , time interval \mathcal{T}^{\prime} and bandwidth K=\rank(\Pi_{\Lambda^{\prime}}) . 2: Output: Optimized \mathcal{V}^{\prime} . 3: Initialize \mathcal{V}^{\prime}=\emptyset . 4: while \lvert\mathcal{V}^{\prime}\rvert\leq K do 5: v^{\ast}=\argmax_{v_{i}}\cos\left(\cos^{-1}\sqrt{\lambda_{\max}\left(\Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}\cup{\{v_{i}\}}}\Pi_{\Lambda^{\prime}}\right)\lambda_{\max}\left(\Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}}\right)}-\cos^{-1}\left(\beta_{\Lambda^{\prime}}\beta_{\Omega^{\prime}}\right)\right) 6: \mathcal{V}^{\prime}\leftarrow\mathcal{V}^{\prime}\cup\{v^{\ast}\} . 7: end while Algorithm 2 Joint energy concentrated dictionary (JECD) learning algorithm 1: Input: Training instances \mathcal{M}_{\mathrm{train}} , training samples \mathbf{Y}_{\mathrm{train}}=\left(y_{m}\right)_{m\in\{1,\dots,M\}} , spectral spread \beta_{\Lambda^{\prime}} , frequency spread \beta_{\Omega^{\prime}} , learning rate \eta_{1} and \eta_{2} , convergence tolerance \epsilon , signal length \delta . 2: Output: Optimized \widetilde{\mathcal{V}} , \widetilde{t_{c}} and \widetilde{\ell} 3: Initialize t_{c}^{0} , \ell^{0} , \mathcal{V}^{\prime}=\emptyset , u=0 . 4: repeat 5: \mathcal{V}^{\prime(u)}\leftarrow algorithm 1 6: \mathbf{x}^{(u)}=\mathrm{Lasso}(\mathbf{Y}_{\mathrm{train}},\Xi(\mathcal{M}_{\mathrm{train}};\mathcal{V}^{\prime(u)},t_{c}^{(u)},\ell^{(u)})) 7: t_{c}^{(u+1)}=t_{c}^{(u)}-\eta_{1}\frac{\partial{}}{\partial{t_{c}^{u}}}\lVert\mathbf{Y}_{\mathrm{train}}-\Xi(\mathcal{M}_{\mathrm{train}};\mathcal{V}^{\prime(u)},t_{c}^{(u)},\ell^{(u)})\mathbf{x}^{(u)}\rVert_{2}^{2} 8: \ell^{(u+1)}=\ell^{(u)}-\eta_{2}\frac{\partial{}}{\partial{\ell^{u}}}\lVert\mathbf{Y}_{\mathrm{train}}-\Xi(\mathcal{M}_{\mathrm{train}};\mathcal{V}^{\prime(u)},t_{c}^{(u)},\ell^{(u)})\mathbf{x}^{(u)}\rVert_{2}^{2} 9: if t_{c}^{(u+1)}\notin[0,\delta] or \ell^{(u+1)}>\delta then 10: t_{c}^{(u+1)}=\max(0,\min(t_{c}^{(u+1)},\delta)) 11: \ell^{(u+1)}=\max(0,\min(\ell^{(u+1)},\delta)) 12: end if 13: u\leftarrow u+1 14: until \lVert\mathrm{Loss}^{(u)}-\mathrm{Loss}^{(u-1)}\rVert\leq\epsilon We use a greedy approach to solve 1(a) , as summarized in algorithm 1 . Given the selected vertex subset \mathcal{V}^{\prime} , we then optimize the continuous dictionary parameters (t_{c},\ell) using the training samples to learn the dictionary \Xi(\mathcal{V}^{\prime},t_{c},\ell) via sparse coding. III-B 2 Optimization of continuous dictionary parameters (t_{c},\ell) With \mathcal{V}^{\prime} fixed, the dictionary learning problem reduces to a sparse coding problem in which only the temporal parameters (t_{c},\ell) and the sparse coefficients \mathbf{x} are optimized. This leads to 1(b) . Problem 1(b) . Given the training measurement set \mathcal{M}_{\mathrm{train}} , and the noisy observations \mathbf{Y}_{\mathrm{train}} , the goal is to learn the dictionary by jointly estimating the sparse coefficients \mathbf{x} and the dictionary parameters (t_{c},\ell) . This leads to the following optimization problem: \displaystyle\begin{aligned} \argmin_{\mathbf{x},t_{c},\ell}\ &\lVert\mathbf{Y}_{\mathrm{train}}-\Xi(\mathcal{M}_{\mathrm{train}};\mathcal{V}^{\prime},t_{c},\ell)\mathbf{x}\rVert_{2}^{2}+\mu\lVert\mathbf{x}\rVert_{1}\\ \ST\ &t_{c}\in[0,\delta],\ 0\leq\ell\leq\delta.\end{aligned} (23) Here, \mathbf{x} contains sparse coefficients, and \mu is a regularization parameter. The optimization problem eq. 23 is not jointly convex but is convex with respect to each variable when the others are fixed. We optimize by alternating minimization over \mathbf{x} , t_{c} and \ell until a convergence criterion. At the u -th iteration, the following minimizations are performed sequentially: \displaystyle\mathbf{x}^{u+1} \displaystyle\leftarrow\argmin_{\mathbf{x}^{u}}\lVert\mathbf{Y}_{\mathrm{train}}-\Xi(\mathcal{M}_{\mathrm{train}};\mathcal{V}^{\prime},t_{c}^{u},\ell^{u})\mathbf{x}^{u}\rVert_{2}^{2}+\mu\lVert\mathbf{x}^{u}\rVert_{1} \displaystyle t_{c}^{u+1} \displaystyle\leftarrow\argmin_{t_{c}^{u}}\lVert\mathbf{Y}_{\mathrm{train}}-\Xi(\mathcal{M}_{\mathrm{train}};\mathcal{V}\textquoteright,t_{c}^{u},\ell^{u})\mathbf{x}^{u+1}\rVert_{2}^{2} \displaystyle\qquad\qquad\ST t_{c}\in[0,\delta] \displaystyle\ell^{u+1} \displaystyle\leftarrow\argmin_{\ell^{u}}\lVert\mathbf{Y}_{\mathrm{train}}-\Xi(\mathcal{M}_{\mathrm{train}};\mathcal{V}^{\prime},t_{c}^{u+1},\ell^{u})\mathbf{x}^{u+1}\rVert_{2}^{2} \displaystyle\qquad\qquad\ST 0\leq\ell\leq\delta. The sparse coefficients \mathbf{x} are updated using Lasso regression [ 39 ] . After updating \mathbf{x} , the dictionary is updated by optimizing t_{c} and \ell using the gradient descent algorithm [ 40 ] . We summarize the complete procedure in algorithm 2 , referred to as joint energy concentrated dictionary (JECD), where Loss denotes the objective function in eq. 22 . Suppose the optimization solution of 1 is given by (\widetilde{\mathcal{V}},\widetilde{t}_{c},\widetilde{\ell}) . With the optimized dictionary \Xi(\cdot;\widetilde{\mathcal{V}},\widetilde{t}_{c},\widetilde{\ell}) , the reconstruction process is formulated as: \displaystyle\argmin_{\mathbf{x}} \displaystyle\lVert\mathbf{Y}_{\mathrm{test}}-\Xi(\mathcal{M}_{\mathrm{test}};\widetilde{\mathcal{V}},\widetilde{t}_{c},\widetilde{\ell})\mathbf{x}\rVert_{2}^{2}+\mu\lVert\mathbf{x}\rVert_{1} (24) where \mathcal{M}_{\mathrm{test}} denotes test instances and \mathbf{Y}_{\mathrm{test}} the corresponding test sample values. Suppose the optimal solution in eq. 24 is given by \mathbf{x}^{*} . The reconstructed vertex-time graph signal is given by \widehat{f}(v,t)=\Xi(\{(v,t)\};\widetilde{\mathcal{V}},\widetilde{t}_{c},\widetilde{\ell})\mathbf{x}^{*} for each (v,t)\in\mathcal{V}\times\mathcal{T} . The recovery performance is measured by the relative square error: \displaystyle\mathrm{RSE}=\frac{\sum_{(v,t)\in\mathcal{M}_{\mathrm{val}}}\left(f(v,t)-\widehat{f}(v,t)\right)^{2}}{\sum_{(v,t)\in\mathcal{M}_{\mathrm{val}}}f(v,t)^{2}}, (25) where \mathcal{M}_{\mathrm{val}} denotes a validation set of sample points. III-C Gaussian subspace basis for vertex-time graph signal reconstruction Consider the closed Gaussian heat–kernel subspace \mathcal{H}_{\VT}=\overline{\spn}\{e^{-\tau_{v}\mathbf{L}}\delta_{v_{0}}\otimes\tfrac{1}{\sqrt{4\pi\tau_{t}}}e^{-\frac{(t-t_{0})^{2}}{4\tau_{t}}}\allowbreak\nonscript\,:\allowbreak\nonscript\,\mathopen{}\allowbreak v_{0}\in\mathcal{V}^{\prime},\;t_{0}\in\mathcal{T}^{\prime}\} , parameterized by diffusion scales \tau_{v},\tau_{t}>0 . Here, \delta_{v_{0}} is the Kronecker delta at vertex v_{0} , e^{-\tau_{v}\mathbf{L}}\delta_{v_{0}} is the graph heat atom spatially localized about v_{0} , and \tfrac{1}{\sqrt{4\pi\tau_{t}}}e^{-(t-t_{0})^{2}/(4\tau_{t})} is the temporal Gaussian kernel centered at time t_{0} . Each atom is separable and centered at (v_{0},t_{0}) , with \tau_{v} and \tau_{t} controlling the spatial and temporal spreads respectively. Let \Pi_{\tau_{v},\tau_{t}} denote the orthogonal projector onto \mathcal{H}_{\VT} . We seek an orthonormal family of jointly bandlimited signals that maximizes vertex–time concentration. Formally, \xi_{i}=\argmax_{\xi_{i}}\ \lVert\Pi_{\tau_{v},\tau_{t}}\xi_{i}\rVert , \ST\lVert\xi_{i}\rVert=1,\Pi_{\Sigma}\xi_{i}=\xi_{i},\langle\xi_{i},\xi_{j}\rangle=0 for j0 is imposed to avoid the trivial solution. The optimization problem eq. 27 is not jointly convex but is convex with respect to each variable when the others are fixed. We solve the problem by alternating minimization over \mathbf{S} , \mathbf{U} and \mathbf{L} until convergence. At the u -th iteration, the following minimizations are performed sequentially: \displaystyle\mathbf{S}^{(u+1)} \displaystyle\leftarrow\argmin_{\mathbf{S}^{(u)}\in\mathcal{B}_{K}}~\lVert\left(\mathbf{U}^{(u)}\right)^{\mathop{\intercal}}\mathbf{Y}-\mathbf{S}^{(u)}\rVert_{F}^{2} \displaystyle\mathbf{U}^{(u+1)} \displaystyle\leftarrow\argmin_{\mathbf{U}^{(u)}}~\lVert\left(\mathbf{U}^{(u)}\right)^{\mathop{\intercal}}\mathbf{Y}-\mathbf{S}^{(u)}\rVert_{F}^{2} \displaystyle\qquad+\gamma\left(\lVert\Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}}\rVert_{2}-\frac{\left(\alpha_{\mathcal{V}^{\prime}}\alpha_{\mathcal{T}^{\prime}}\right)^{2}}{\lambda_{\max}(\Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}})}\right)^{2} \displaystyle\qquad\ST\Pi_{\Lambda^{\prime}}=\mathbf{U}^{(u)}\Sigma_{\Lambda^{\prime}}\left(\mathbf{U}^{(u)}\right)^{\mathop{\intercal}},\ \mathbf{U}^{(u)}\left(\mathbf{U}^{(u)}\right)^{\mathop{\intercal}}=\mathbf{I} \displaystyle\qquad\qquad~\mathbf{u}_{1}^{(u)}=\bm{1}/\sqrt{N}, \displaystyle\mathbf{L}^{(u+1)} \displaystyle\leftarrow\argmin_{\mathbf{L}^{(u)}}\text{tr}(\mathbf{Y}\mathbf{L}^{(u)}\mathbf{Y}^{\mathop{\intercal}})+\mu\lVert\mathbf{L}^{(u)}\rVert_{F}^{2}, \displaystyle\qquad\ST\mathbf{L}^{(u)}\in\mathcal{L},\text{tr}(\mathbf{L}^{(u)})=p,\ \mathbf{L}^{(u)}\mathbf{U}^{(u)}=\mathbf{U}^{u}\Lambda, \displaystyle\qquad\qquad\Lambda\succeq\textbf{0},\Lambda_{ij}=\Lambda_{ji}=0,\forall\,i\neq j. The complete procedure is summarized in algorithm 3 , referred to as energy-concentrated graph learning (ECGL) . With the optimization solution \widetilde{\mathbf{L}} , we measure performance using the correlation coefficient between the true Laplacian entries L_{ij} and their estimates \tilde{L}_{ij} : \displaystyle\rho(\mathbf{L},\widetilde{\mathbf{L}})\triangleq\frac{\sum_{ij}L_{ij}\tilde{L}_{ij}}{\sqrt{\sum_{ij}L_{ij}^{2}}\sqrt{\sum_{ij}\tilde{L}_{ij}^{2}}}. (28) We evaluate the topology inference using the average recovery error of the adjacency matrix: \displaystyle\bar{\varepsilon}_{F}\triangleq\frac{\lVert\mathbf{A}-\widetilde{\mathbf{A}}\rVert_{F}}{N(N-1)}, (29) where \mathbf{A} is the ground-truth binary adjacency matrix and \widetilde{\mathbf{A}} is derived from \widetilde{\mathbf{L}} . We also adopt edge precision and recall [ 41 ] , which quantify the proportion of correctly detected edges and the proportion of true edges recovered. Defining \mathcal{E}_{g} and \mathcal{E}_{r} as the ground-truth and recovered edge sets, respectively, these metrics are: \displaystyle\text{Precision}=\frac{\lvert\mathcal{E}_{g}\cap\mathcal{E}_{r}\rvert}{\lvert\mathcal{E}_{r}\rvert},\quad\text{Recall}=\frac{\lvert\mathcal{E}_{g}\cap\mathcal{E}_{r}\rvert}{\lvert\mathcal{E}_{g}\rvert}. (30) V Experimental Results V-A Vertex-time graph signal reconstruction We validate our theoretical developments via numerical experiments on three tasks. First, we evaluate JECD for vertex–time signal reconstruction and compare it against several baselines using two real datasets: the California COVID - 19 county case counts and the California traffic flow measurements. Second, we assess the Gaussian heat - kernel subspace basis on synthetic vertex–time signals to quantify its reconstruction accuracy and noise robustness. Third, we test ECGL on a synthetic graph for topology inference and compare it with state - of - the - art graph learning algorithms. V-A 1 Support-limited subspace case We split each data set into training and test sets. The JECD \Xi is trained using a proportion p_{o} of the training samples. We then reconstruct the test set by using p_{o} of its samples and measure performance on the remaining 1-p_{o} . We compare our approach with the following vertex-time dictionaries for vertex-time graph signal reconstruction: 1. Joint Fourier transform (JFT) [ 19 ] : The JFT dictionary is constructed from a set of joint vertex-time Fourier bases \{\phi_{k}\otimes\psi_{l}\nonscript\,:\allowbreak\nonscript\,\mathopen{}k=1,\dots,K,\ l=1,\dots,L\} . Here, \phi_{k} is the k -th orthonormal eigenvector of the graph Laplacian \mathbf{L} , and \psi_{l} is an element of the orthonormal Fourier basis in the time domain, given by \{\frac{1}{\sqrt{2\pi}},\frac{1}{\sqrt{\pi}}\cos(lt),\frac{1}{\sqrt{\pi}}\sin(lt)\}_{l\geq 1} . Both K and L are tunable hyperparameters. 2. STVFT [ 23 ] : We design the mother vertex-time kernel in the short time-vertex Fourier basis in a separable manner. In the vertex domain, following [ 23 ] , the localized graph basis is \mathbf{h}_{p,q}=(\mathbf{U}h(\Lambda-\Lambda_{q})\mathbf{U}^{\ast})\bm{\delta}_{p} , where h(\cdot) is adopted as an Itersine kernel [ 42 ] , given by h(\Lambda)=\sin(0.5\pi\cos((\pi\Lambda)^{2}) with uniformly Q translations \Lambda_{q}=\diag(\frac{\lambda_{\max}}{Q}q) for q=1,\ldots,Q . Here, \mathbf{U} is the unitary matrix whose columns are the Laplacian eigenvectors, \Lambda is a diagonal matrix with non-negative real eigenvalues \{\lambda_{i}\}_{i=1,\dots,N} , and \bm{\delta}_{p} is a Kronecker delta centered at vertex p . In the time domain, we use Gabor functions g_{m,n}(t)=\frac{1}{\sqrt{2\pi}\rho}e^{-\frac{(t-m\tau_{0})^{2}}{2\rho^{2}}}e^{jn\omega_{0}} where m,n\in\mathbb{Z} , \tau_{0} and \omega_{0} are time and frequency shifts, and \rho controls the Gaussian window width. The STVFT dictionary is constructed from the short-time-vertex Fourier bases \{\mathbf{h}_{p,q}\otimes g_{m,n}(t)\}_{p,q,m,n} . The parameters Q , \tau_{0} , \omega_{0} , and \sigma are tunable hyperparameters. 3. STVWT [ 23 ] : The mother vertex-time kernel in the spectral time-vertex wavelet basis is also designed in a separable manner. For the vertex dimension, the localized graph wavelet basis is \mathbf{h}_{p,s}=(\mathbf{U}h(s\Lambda)\mathbf{U}^{\ast})\bm{\delta}_{p} , where h(s\Lambda) is the scaled Itersine kernel [ 42 ] and \bm{\delta}_{p} is a Kronecker delta centered at vertex p\in\mathcal{V} . For the time dimension, we use a Morlet wavelet \psi_{a,b}(t)=\frac{1}{\sqrt{a}}e^{-\frac{(t-b)^{2}}{2a^{2}}}e^{j\omega_{0}\frac{t-b}{a}} with a>0 and b\in\mathbb{R} as the scale and translation parameters, controlling dilation and time shift respectively, and \omega_{0} as the central frequency. The STVWT dictionary is constructed from a collection of \{\mathbf{h}_{p,s}\otimes\psi_{a,b}(t)\}_{p,s,a,b} . Here, s , a and b are tunable hyperparameters. 4. Naive extension of GUP (NEGUP) [ 16 ] : In the vertex domain, the graph localized basis is \Phi(\mathcal{V}^{\prime})=\left(\phi_{k}(\cdot;\mathcal{V}^{\prime})\right)_{k\geq 1} , where for each k\geq 1 , \phi_{k}(\cdot;\mathcal{V}^{\prime}):\mathcal{V}\rightarrow\mathbb{R} is an eigenvector of \Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}} , which is a graph signal localized over \mathcal{V}^{\prime} . Here \mathcal{V}^{\prime} is determined by the right upper bound of the feasible region, shown in Theorem 2.1 in [ 16 ] , as follows \displaystyle\argmax_{\mathcal{V}^{\prime}}\ \displaystyle\cos\left(\cos^{-1}\sqrt{\lambda_{\max}\left(\Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}}\right)}-\cos^{-1}\beta_{\Lambda^{\prime}}\right) \displaystyle\ST\ \displaystyle\lvert\mathcal{V}^{\prime}\rvert\leq K,\ K=\rank(\Pi_{\Lambda^{\prime}}). In the time domain, the localized basis is \Psi(\mathcal{T}^{\prime})=\left(\psi_{n}(\cdot;\mathcal{T}^{\prime})\right)_{n\geq 1} , where for each n\geq 1 , \psi_{n}(\cdot;\mathcal{T}^{\prime}):\mathcal{T}\rightarrow\mathbb{R} is a PSWF localized over \mathcal{T}^{\prime} . Each \psi_{n}(\cdot;\mathcal{T}^{\prime}) is an eigenfunction of \Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}} . Here \mathcal{T}^{\prime} is predefined by the signal’s length, denoted as \mathcal{T}^{\prime}=[-\ell/2,\ell/2] . The NEGUP dictionary is constructed by \Phi(\mathcal{V}^{\prime})\otimes\Psi(\mathcal{T}^{\prime}) . We evaluate vertex-time signal reconstruction on a COVID-19 dataset from The New York Times, which compiles reports from state and local health agencies. 3 3 3 https://github.com/TorchSpatiotemporal/tsl We extract records for California’s 58 counties from the first day each reported cases, spanning July 29, 2020, to August 1, 2022. The data is split into a training set \mathcal{M}_{\mathrm{train}} (July 29, 2020–July 30, 2021) and a test set \mathcal{M}_{\mathrm{test}} (July 31, 2021–August 1, 2022). Each county is treated as a vertex, with edges connecting adjacent counties. We randomly select a proportion p_{o} of the training samples to optimize the dictionary \Xi . We then reconstruct the test set using p_{o} of its samples and evaluate the performance on the remaining 1-p_{o} proportion according to eq. 25 . (a) Varying training ratios and no additive noise. (b) Varying SNR and fixed training ratio of 0.2 . Fig. 3 : Reconstruction error over test set under different conditions. Each point in the figure is obtained by 10 repetitions. By setting different values of \beta_{\Lambda^{\prime}} at 99\% , 97\% , 95\% , and 92.5\% , the resulting sets \mathcal{V}^{\prime} have cardinalities of 48 , 38 , 28 , and 18 , respectively, for both JECD and NEGUP. Figure 3 and Figure 3 show the effect of \beta_{\Lambda^{\prime}} on reconstruction performance across training ratios from 0.1 to 0.2 and SNR levels from 0 dB to 10 dB. JECD consistently outperforms NEGUP under all conditions, with the highest accuracy achieved when \lvert\mathcal{V}^{\prime}\rvert=48 . These findings confirm JECD’s ability to exploit temporal dependencies and adapt to time-varying data, resulting in a more effective dictionary design than NEGUP’s static graph-based approach. To further highlight JECD’s advantages, it is also compared against JFT, STVFT, and STVWT. Figure 4 shows that JECD maintains the lowest RSE across various training ratios and SNR levels, demonstrating robust performance in noisy and dynamic scenarios and confirming its overall superiority among the tested methods. (a) RSE with varying training ratios and no additive noise. (b) RSE with varying SNR levels and a fixed training ratio of 0.2 . Fig. 4 : Reconstruction error under varying conditions. Each data point is the average of 10 experiments. V-A 2 Gaussian subspace case We evaluate the Gaussian heat-kernel subspace basis on synthetic data. An Erdős-Rènyi graph with N=40 nodes and connection probability 0.5 is generated. The ground-truth vertex–time signal is (K,\omega_{0}) -bandlimited and defined by y=\sum_{i=1}^{K}\mathbf{u}_{i}\otimes f , where \mathbf{u}_{i} is the i -th eigenvector of \mathbf{L} and f=2\frac{\sin(\omega_{0}t)}{(\omega_{0}t)}-\frac{\sin((\omega_{0}-2)t)}{((\omega_{0}-2)t)}+\frac{\sin((\omega_{0}-4)t)}{2((\omega_{0}-4)t)} . We set K=2 and \omega_{0}=10 , and sample M=300 uniformly spaced time points over t\in[-2.5,2.5] (see fig. 5(a) ). Visual inspection of the ground-truth heat map motivates placing the Gaussian-subspace atom center at (v_{0},t_{0})=(36,0) . Given candidate diffusion scales \mathcal{P}_{v}=\{1,0.5,0.1,0.01\} and \mathcal{P}_{t}=\{1,0.5,0.1,0.01\} , and the optimal pair (\tau_{v}^{\star},\tau_{t}^{\star})=(0.1,0.01) is chosen via eq. 26 . With this choice, we form \mathbf{A}^{\star}=\Pi_{\Sigma}\Pi_{\tau_{v}^{\star},\tau_{t}^{\star}}\Pi_{\Sigma} , and the leading eigenvectors of \mathbf{A}^{\star} form an orthonormal basis of \Sigma=(K,\omega_{0}) -bandlimited signals that is maximally concentrated in the vertex-time domain. To assess noise robustness, we create the observed graph signal by adding Gaussian noise to the ground truth graph signal with different SNR levels ranging from -8 db to 2 db. We compare the proposed basis with JFT, STVFT, and STVWT under the same graph bandwidth K=2 and (time) bandlimit \omega_{0}=10 . For each method, we reconstruct by projecting the noisy observation onto that method’s span. As observed in fig. 5(b) , the Gaussian heat-kernel subspace basis achieves the lowest RSE across all tested SNRs, outperforming competing methods even at low SNR and remaining the top performer as SNR increases. (a) Heat map of the power of the ground-truth graph signal. (b) RSE with varying SNR levels. Fig. 5 : Ground-truth graph siganl and reconstruction error under varying SNR levels. V-B Graph topology inference results We examine the effectiveness of ECGL on a synthetic graph created using an Erdős-Rènyi graph with N=20 nodes and a connection probability of 0.4 . The vertex-time graph signal is (K,\omega_{0}) bandlimited, and we construct it as y=\sum_{i=1}^{K}\mathbf{u}_{i}\otimes f , where \mathbf{u}_{i} is the i -th eigenvector of \mathbf{L} and f=\sin(\omega_{0}t)/(\omega_{0}t) . We set K=3 and \omega_{0}=10 and evaluate the signal over M=1000 time instances. We then compare ECGL with two existing graph learning methods, Total Variation Graph Learning (TV-GL) [ 27 ] and Estimated-Signal-Aided Graph Learning (ESA-GL) [ 27 ] , using the performance metrics in eq. 28 , eq. 29 , and eq. 30 . The results, summarized in table I , indicate that ECGL achieves the highest correlation coefficient with stronger alignment between the learned and true Laplacians. It also attains the lowest average recovery error, reflecting more accurate adjacency matrix estimation. Additionally, ECGL outperforms both TV-GL and ESA-GL in Precision and Recall, with a particularly notable improvement in Recall, which demonstrates its enhanced capability to recover true edges in the graph. TABLE I : Performance comparison on graph topology reference. \uparrow and \downarrow indicate higher and lower values are better, respectively. TV-GL ESA-GL ECGL \rho(\mathbf{L},\widetilde{\mathbf{L}})\uparrow 0.9274 0.9267 0.9288 \bar{\varepsilon}_{F}\downarrow 0.0370 0.0368 0.0363 Precision \uparrow 0.4338 0.4370 0.4500 Recall \uparrow 0.7284 0.7284 0.7780 VI Conclusion This paper establishes an uncertainty principle for vertex-time graph signals, unifying classical time-frequency and graph uncertainty principles. By defining vertex-time and spectral-frequency spreads, we quantify signal localization and identify maximally concentrated signals for constructing a vertex-time dictionary. This dictionary improves signal reconstruction, particularly under missing or intermittent data. Additionally, we introduce a graph topology inference method based on the uncertainty principle. Numerical experiments on synthetic and real datasets demonstrate superior reconstruction accuracy, noise robustness, and graph learning performance compared to existing methods. Future work will explore extensions to dynamic and large-scale graphs, further broadening the applicability of the proposed framework. Appendix A Proof of 1 Before proving the theorem, we present several technical preliminary results adapted from [ 16 ] and [ 3 ] . The proofs essentially follow the same procedure as in [ 4 ] for continuous-time signals and are repeated here for completeness. Definition A.1 . The angle between two functions f and g belonging to a Hilbert space is defined as \displaystyle\theta(f,g)=\cos^{-1}\frac{\Re\{\langle f,g\rangle\}}{\lVert f\rVert\lVert g\rVert} (31) where \langle\cdot,\cdot\rangle and \lVert\cdot\rVert are the Hilbert space inner product and norm, respectively. Lemma A.1 . For a given function f\in\ima(\Pi_{\SF}) , \displaystyle\inf_{g\in\ima(\Pi_{\VT})}\theta(f,g)=\cos^{-1}\frac{\lVert\Pi_{\VT}f\rVert}{\lVert f\rVert} is achieved by g=k\cdot\Pi_{\VT}f for any constant k>0 . Proof. For any g\in\ima(\Pi_{\VT}) , we have \displaystyle\begin{aligned} \Re\{\langle f,g\rangle\}\leq\lvert\langle f,g\rangle\rvert&=\lvert\langle f-\Pi_{\VT}f+\Pi_{\VT}f,g\rangle\rvert\\ &=\lvert\langle\Pi_{\VT}f,g\rangle\rvert\leq\lVert\Pi_{\VT}f\rVert\lVert g\rVert\end{aligned} where the second equality holds due to the fact that f-\Pi_{\VT}f is orthogonal to g , and third equality is due to the Cauchy–Schwarz inequality. We thus have \displaystyle\cos\theta(f,g)=\frac{\Re\{\langle f,g\rangle\}}{\lVert f\rVert\lVert g\rVert}\leq\frac{\lVert\Pi_{\VT}f\rVert\lVert g\rVert}{\lVert f\rVert\lVert g\rVert}=\frac{\lVert\Pi_{\VT}f\rVert}{\lVert f\rVert}. (32) Since \cos\theta decreases monotonically in [0,\pi] and equality in eq. 32 is achieved by choosing g=k\cdot\Pi_{\VT}f with k>0 , it follows that \displaystyle\inf_{g\in\ima(\Pi_{\VT})}\theta(f,g)=\cos^{-1}\frac{\lVert\Pi_{\VT}f\rVert}{\lVert f\rVert}. ∎ We define the minimum angle between \ima(\Pi_{\SF}) and \ima(\Pi_{\VT}) as \displaystyle\theta_{\min}=\inf_{f\in\ima(\Pi_{\SF}),g\in\ima(\Pi_{\VT})}\theta(f,g). (33) Proposition A.1 ( [ 43 ] ) . The minimum angle \theta_{\min} between \ima(\Pi_{\SF}) and \ima(\Pi_{\VT}) is given by \displaystyle\theta_{\min}=\cos^{-1}\sqrt{\lambda_{\max}\left(\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}\right)}, and is achieved by choosing f=\psi_{0} and g=\Pi_{\VT}\psi_{0} in eq. 33 , where \psi_{0} is an eigenvector of the Hermitian operator \Pi_{\SF}\Pi_{\VT}\Pi_{\SF} corresponding to the eigenvalue \lambda_{\max}(\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}) . Proof. From A.1 , we have \displaystyle\begin{aligned} &\inf_{f\in\ima(\Pi_{\SF}),~g\in\ima(\Pi_{\VT})}\theta(f,g)\\ &\qquad\qquad=\inf_{f\in\ima(\Pi_{\SF})}\cos^{-1}\frac{\lVert\Pi_{\VT}f\rVert}{\lVert f\rVert}\\ &\qquad\qquad=\cos^{-1}\sup_{f\in\ima(\Pi_{\SF})}\frac{\lVert\Pi_{\VT}f\rVert}{\lVert f\rVert},\end{aligned} since \cos(\cdot) decreases monotonically in [0,\pi] . For any f\in\ima(\Pi_{\SF}) , \Pi_{\SF}f=f , and we have \displaystyle\begin{aligned} \frac{\lVert\Pi_{\VT}f\rVert^{2}}{\lVert f\rVert^{2}}&=\frac{\lVert\Pi_{\VT}\Pi_{\SF}f\rVert^{2}}{\lVert f\rVert^{2}}=\frac{\langle\Pi_{\VT}\Pi_{\SF}f,\Pi_{\VT}\Pi_{\SF}f\rangle}{\langle f,f\rangle}\\ &=\frac{\langle f,\Pi_{\SF}^{\ast}\Pi_{\VT}^{\ast}\Pi_{\VT}\Pi_{\SF}f\rangle}{\langle f,f\rangle}.\end{aligned} (34) Since \Pi_{\SF} and \Pi_{\VT} are both Hermitian and idempotent operators, eq. 34 yields \displaystyle\frac{\lVert\Pi_{\VT}f\rVert^{2}}{\lVert f\rVert^{2}}=\frac{\langle f,\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}f\rangle}{\langle f,f\rangle}. From the Rayleigh-Ritz theorem [ 44 ] , we obtain \displaystyle\begin{aligned} \sup_{f}\frac{\lVert\Pi_{\VT}f\rVert^{2}}{\lVert f\rVert^{2}}&=\sup_{f}\frac{\langle f,\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}f\rangle}{\langle f,f\rangle}\\ &=\lambda_{\max}(\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}),\end{aligned} (35) and the proposition is proved. ∎ We are now ready to prove 1 . Without loss of generality, we derive which values of \beta_{\SF} are attainable for every choice of \alpha_{\VT} , assuming a unit-norm signal f . We consider two cases \alpha_{\VT}=1 and \alpha_{\VT}\in(0,1) . The case \alpha_{\VT}=1 means that the signal f is supported only on the closure of \mathcal{H}_{\VT} . From eq. 35 (by interchanging \Pi_{\SF} and \Pi_{\VT} ) and A.1 , we obtain \displaystyle\sup_{f\in\ima(\Pi_{\VT}),\lVert f\rVert=1}\beta_{\SF}^{2}=\lambda_{\max}(\Pi_{\VT}\Pi_{\SF}\Pi_{\VT}). (36) Similarly, \displaystyle\inf_{f\in\ima(\Pi_{\VT}),\lVert f\rVert=1}\beta_{\SF}^{2}=1-\lambda_{\max}(\Pi_{\VT}\overline{\Pi}_{\SF}\Pi_{\VT}) (37) which is equivalent to the case of maximal concentration on the orthogonal complement subspace \mathcal{H}_{\SF}^{\perp} . Thus, in the case of \alpha_{\VT}=1 , \beta_{\SF}^{2} lies in the interval [1-\lambda_{\max}(\Pi_{\VT}\overline{\Pi}_{\SF}\Pi_{\VT}),\lambda_{\max}(\Pi_{\VT}\Pi_{\SF}\Pi_{\VT})] . Next, suppose \alpha_{\VT}\in(0,1) . We can decompose any signal f as \displaystyle f=\lambda\Pi_{\VT}f+\gamma\Pi_{\SF}f+g (38) where g is a signal orthogonal to both \ima(\Pi_{\VT}) and \ima(\Pi_{\SF}) . Our goal is to find the nearest signal to f in the space spanned by \Pi_{\VT}f and \Pi_{\SF}f . To do this, we firstly calculate the inner products of eq. 38 successively with f , \Pi_{\VT}f , \Pi_{\SF}f and g , and arrive at the system of equations: \displaystyle\centering\left\{\begin{aligned} &1=\lambda\alpha_{\VT}^{2}+\gamma\beta_{\SF}^{2}+\langle g,f\rangle,\\ &\alpha_{\VT}^{2}=\lambda\alpha_{\VT}^{2}+\gamma\langle\Pi_{\SF}f,\Pi_{\VT}f\rangle,\\ &\beta_{\SF}^{2}=\lambda\langle\Pi_{\VT}f,\Pi_{\SF}f\rangle+\gamma\beta_{\SF}^{2},\\ &\langle f,g\rangle=\langle g,g\rangle.\end{aligned}\right.\@add@centering (39) After eliminating \langle g,f\rangle , \lambda and \gamma from eq. 39 , we obtain \displaystyle\begin{aligned} &\beta_{\SF}^{2}-2\Re\{\langle\Pi_{\VT}f,\Pi_{\SF}f\rangle+\alpha_{\VT}^{2}\\ &=\left(1-\frac{\lvert\langle\Pi_{\VT}f,\Pi_{\SF}f\rangle\rvert^{2}}{\alpha_{\VT}^{2}\beta_{\SF}^{2}}\right)-\lVert g\rVert^{2}\left(1-\frac{\lvert\langle\Pi_{\VT}f,\Pi_{\SF}f\rangle\rvert^{2}}{\alpha_{\VT}^{2}\beta_{\SF}^{2}}\right).\end{aligned} (40) From A.1 , the angle \theta between \Pi_{\VT}f\in\ima(\Pi_{\VT}) and \Pi_{\SF}f\in\ima(\Pi_{\SF}) satisfies \displaystyle\theta\geq\cos^{-1}\sqrt{\lambda_{\max}\left(\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}\right)}=\cos^{-1}\lambda_{\max}\left(\Pi_{\VT}\Pi_{\SF}\right). (41) Since \lVert\Pi_{\VT}f\rVert=\alpha_{\VT} , \lVert\Pi_{\SF}f\rVert=\beta_{\SF} , eq. 31 gives \displaystyle\begin{aligned} \alpha_{\VT}\beta_{\SF}\cos\theta&=\Re\{\langle\Pi_{\VT}f,\Pi_{\SF}f\rangle\}\\ &\leq\lvert\langle\Pi_{\VT}f,\Pi_{\SF}f\rangle\rvert\leq\alpha_{\VT}\beta_{\SF},\end{aligned} (42) and we can further write \displaystyle 0\leq 1-\frac{\lvert\langle\Pi_{\VT}f,\Pi_{\SF}f\rangle\rvert^{2}}{\alpha_{\VT}^{2}\beta_{\SF}^{2}}\leq 1-\cos^{2}\theta. (43) Completing the square on the left-hand side of eq. 40 , and applying eq. 43 , we obtain \displaystyle\begin{aligned} (\beta_{\SF}&-\alpha_{\VT}\cos\theta)^{2}\\ &=-\alpha_{\VT}^{2}\sin^{2}\theta+\left(1-\frac{\lvert\langle\Pi_{\VT}f,\Pi_{\SF}f\rangle\rvert^{2}}{\alpha_{\VT}^{2}\beta_{\SF}^{2}}\right)\\ &\qquad\qquad-\lVert g\rVert^{2}\left(1-\frac{\lvert\langle\Pi_{\VT}f,\Pi_{\SF}f\rangle\rvert^{2}}{\alpha_{\VT}^{2}\beta_{\SF}^{2}}\right)\\ &\leq-\alpha_{\VT}^{2}\sin^{2}\theta+1-\cos^{2}\theta\\ &=(1-\alpha_{\VT}^{2})\sin^{2}\theta=\sin^{2}(\cos^{-1}\alpha_{\VT})\sin^{2}\theta,\end{aligned} where equality holds in the last inequality if and only if \langle\Pi_{\VT}f,\Pi_{\SF}f\rangle is real and g=0 (a.e.). Therefore, \displaystyle\beta_{\SF}\leq\cos(\theta-\cos^{-1}\alpha_{\VT}), from which it follows, by means of the bound eq. 41 , that \displaystyle\beta_{\SF}\leq\cos(\cos^{-1}\sqrt{\lambda_{\max}\left(\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}\right)}-\cos^{-1}\alpha_{\VT}). Thus, \displaystyle\cos^{-1}\alpha_{\VT}+\cos^{-1}\beta_{\SF}\geq\cos^{-1}\sqrt{\lambda_{\max}(\Pi_{\SF}\Pi_{\VT}\Pi_{\SF})}, (44) where equality is achieved by \displaystyle f=p\psi_{0}+q\Pi_{\VT}\psi_{0} with \displaystyle p \displaystyle=\sqrt{\frac{1-\alpha_{\VT}^{2}}{1-\lambda_{\max}(\Pi_{\SF}\Pi_{\VT}\Pi_{\SF})}}, \displaystyle q \displaystyle=\frac{\alpha_{\VT}}{\sqrt{\lambda_{\max}(\Pi_{\SF}\Pi_{\VT}\Pi_{\SF})}}-\sqrt{\frac{1-\alpha_{\VT}^{2}}{1-\lambda_{\max}(\Pi_{\SF}\Pi_{\VT}\Pi_{\SF})}} and \psi_{0} is an eigenvector of the Hermitian operator \Pi_{\SF}\Pi_{\VT}\Pi_{\SF} corresponding to the eigenvalue \lambda_{\max}(\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}) . Using \lVert\overline{\Pi}_{\VT}f\rVert=\sqrt{1-\alpha_{\VT}^{2}} and applying the same steps between eq. 38 and eq. 44 to the operators \Pi_{\SF}\overline{\Pi}_{\VT}\Pi_{\SF} , we obtain the inequality \displaystyle\cos^{-1}\sqrt{1-\alpha_{\VT}^{2}}+\cos^{-1}\beta_{\SF}\geq\cos^{-1}\sqrt{\lambda_{\max}(\Pi_{\SF}\overline{\Pi}_{\VT}\Pi_{\SF})}. Similarly, with \lVert\overline{\Pi}_{\SF}f\rVert=\sqrt{1-\beta_{\SF}^{2}} , we have \displaystyle\cos^{-1}\alpha_{\VT}+\cos^{-1}\sqrt{1-\beta_{\SF}^{2}}\geq\cos^{-1}\sqrt{\lambda_{\max}(\overline{\Pi}_{\SF}\Pi_{\VT}\overline{\Pi}_{\SF})} and \displaystyle\begin{aligned} \cos^{-1}\sqrt{1-\alpha_{\VT}^{2}}&+\cos^{-1}\sqrt{1-\beta_{\SF}^{2}}\\ &\geq\cos^{-1}\sqrt{\lambda_{\max}(\overline{\Pi}_{\SF}\overline{\Pi}_{\VT}\overline{\Pi}_{\SF})}.\end{aligned} We have now verified the four inequalities in eq. 7 . For \beta_{\SF}=1 , \alpha_{\VT}^{2} lies in the interval [1-\lambda_{\max}(\Pi_{\SF}\overline{\Pi}_{\VT}\Pi_{\SF}),\lambda_{\max}(\Pi_{\SF}\Pi_{\VT}\Pi_{\SF})] , achieved by the eigenvectors of \Pi_{\SF}\Pi_{\VT}\Pi_{\SF} that belong to \Pi_{\SF} and their linear combinations. Proceeding similarly, one can show that all the values \alpha_{\VT} and \beta_{\SF} belonging to the border of \Theta are achievable. All the points inside \Theta are achievable different combinations of the left and right singular vectors of \Pi_{\SF}\Pi_{\VT}\Pi_{\SF} , \Pi_{\SF}\overline{\Pi}_{\VT}\Pi_{\SF} , \overline{\Pi}_{\SF}\Pi_{\VT}\overline{\Pi}_{\SF} and \overline{\Pi}_{\SF}\overline{\Pi}_{\VT}\overline{\Pi}_{\SF} . This concludes the proof of 1 . Appendix B Proof of 1 Using the fact that \lVert f\rVert^{2}_{L^{2}(\mathcal{V}\times\mathcal{T})}=\sum_{v\in\mathcal{V}}\lVert f(v,\cdot)\rVert_{L^{2}(\mathcal{T})}^{2}=\int_{\mathcal{T}}\lVert f(\cdot,t)\rVert_{L^{2}(\mathcal{V})}^{2}\,\mathrm{d}t , we have \displaystyle\alpha_{\mathcal{S}}^{2} \displaystyle=\frac{\lVert f\rVert^{2}_{L^{2}(\mathcal{S})}}{\lVert f\rVert^{2}_{L^{2}(\mathcal{V}\times\mathcal{T})}}=\frac{\sum_{v\in\mathcal{V}^{\prime}}\int_{\mathcal{T}^{\prime}}\lvert f(v,t)\rvert^{2}\,\mathrm{d}t}{\sum_{v\in\mathcal{V}}\int_{\mathcal{T}}\lvert f(v,t)\rvert^{2}\,\mathrm{d}t} \displaystyle=\frac{\int_{\mathcal{T}^{\prime}}\lVert f(\cdot,t)\rVert_{L^{2}(\mathcal{V}^{\prime})}^{2}\,\mathrm{d}t}{\int_{\mathcal{T}^{\prime}}\lVert f(\cdot,t)\rVert_{L^{2}(\mathcal{V})}^{2}\,\mathrm{d}t}\frac{\sum_{v\in\mathcal{V}}\lVert f(v,\cdot)\rVert_{L^{2}(\mathcal{T}^{\prime})}^{2}}{\sum_{v\in\mathcal{V}}\lVert f(v,\cdot)\rVert_{L^{2}(\mathcal{T})}^{2}} (45) and \displaystyle\beta_{\Sigma}^{2} \displaystyle=\frac{\lVert\mathcal{U}f\rVert_{L^{2}(\Sigma)}^{2}}{\lVert\mathcal{U}f\rVert^{2}_{L^{2}(\Lambda\times\Omega)}}=\frac{\sum_{\lambda\in\Lambda^{\prime}}\int_{\Omega^{\prime}}\lvert\mathcal{U}f(\lambda,\omega)\rvert^{2}\,\mathrm{d}\omega}{\sum_{\lambda\in\Lambda}\int_{\Omega}\lvert\mathcal{U}f(\lambda,\omega)\rvert^{2}\,\mathrm{d}\omega} \displaystyle=\frac{\int_{\Omega^{\prime}}\lVert\mathcal{U}f(\cdot,\omega)\rVert_{L^{2}(\Lambda^{\prime})}^{2}\,\mathrm{d}\omega}{\int_{\Omega^{\prime}}\lVert\mathcal{U}f(\cdot,\omega)\rVert_{L^{2}(\Lambda)}^{2}\,\mathrm{d}\omega}\frac{\sum_{\lambda\in\Lambda}\lVert\mathcal{U}f(\lambda,\cdot)\rVert_{L^{2}(\Omega^{\prime})}^{2}}{\sum_{\lambda\in\Lambda}\lVert\mathcal{U}f(\lambda,\cdot)\rVert_{L^{2}(\Omega)}^{2}}. (46) Since \displaystyle\min_{v}\alpha^{2}_{\mathcal{T}^{\prime}}(v)\leq\frac{\sum_{v\in\mathcal{V}}\lVert f(v,\cdot)\rVert_{L^{2}(\mathcal{T}^{\prime})}^{2}}{\sum_{v\in\mathcal{V}}\lVert f(v,\cdot)\rVert_{L^{2}(\mathcal{T})}^{2}}\leq\max_{v}\alpha^{2}_{\mathcal{T}^{\prime}}(v) and \displaystyle\inf_{t}\alpha^{2}_{\mathcal{V}^{\prime}}(t)\leq\frac{\int_{\mathcal{T}^{\prime}}\lVert f(\cdot,t)\rVert_{\ell^{2}(\mathcal{V}^{\prime})}^{2}\,\mathrm{d}t}{\int_{\mathcal{T}^{\prime}}\lVert f(\cdot,t)\rVert_{\ell^{2}(\mathcal{V})}^{2}\,\mathrm{d}t}\leq\sup_{t}\alpha^{2}_{\mathcal{V}^{\prime}}(t), the vertex-time spread \alpha^{2}_{\mathcal{S}} in eq. 45 is bounded by \displaystyle\min_{v}\alpha^{2}_{\mathcal{T}^{\prime}}(v)\inf_{t}\alpha^{2}_{\mathcal{V}^{\prime}}(t)\leq\alpha^{2}_{\mathcal{S}}\leq\max_{v}\alpha^{2}_{\mathcal{T}^{\prime}}(v)\sup_{t}\alpha^{2}_{\mathcal{V}^{\prime}}(t). A similar argument bounds the spectral-frequency spread \beta^{2}_{\Sigma} in eq. 46 by \displaystyle\min_{\lambda}\beta^{2}_{\Omega^{\prime}}(\lambda)\inf_{\omega}\beta_{\Lambda^{\prime}}^{2}(\omega)\leq\beta^{2}_{\Sigma}\leq\max_{\lambda}\beta^{2}_{\Omega^{\prime}}(\lambda)\sup_{\omega}\beta_{\Lambda^{\prime}}^{2}(\omega), and the proof is complete. Appendix C Proof of 2 Consider such two subsets \mathcal{S}=\mathcal{V}^{\prime}\times\mathcal{T}^{\prime} and \Sigma=\Lambda^{\prime}\times\Omega^{\prime} . In this case, the vertex-time limiting operator \Pi_{\mathcal{S}} and spectral-frequency limiting operator \Pi_{\Sigma} could be written as \Pi_{\mathcal{S}}=\Pi_{\mathcal{V}^{\prime}}\otimes\Pi_{\mathcal{T}^{\prime}} and \Pi_{\Sigma}=\Pi_{\Lambda^{\prime}}\otimes\Pi_{\Omega^{\prime}} , respectively. Based on the range of the spectral-frequency spread \beta^{2}_{\Sigma} illustrated in eq. 11 as well as the monotonicity of \cos^{-1} , then the supremum of \alpha_{\mathcal{S}} achieves at \displaystyle\begin{aligned} \alpha_{\mathcal{S}}\leq\cos&\Big(\cos^{-1}\sqrt{\lambda_{\max}\left(\Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}}\right)\lambda_{\max}\left(\Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}}\right)}\\ &\qquad\qquad-\cos^{-1}\left(\beta_{\Lambda^{\prime}}^{\min}\beta_{\Omega^{\prime}}^{\min}\right)\Big)\end{aligned} along with the property of tensor product (\Pi_{\mathcal{V}^{\prime}}\otimes\Pi_{\mathcal{T}^{\prime}})(\Pi_{\Lambda^{\prime}}\otimes\Pi_{\Omega^{\prime}})(\Pi_{\mathcal{V}^{\prime}}\otimes\Pi_{\mathcal{T}^{\prime}})=(\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}})\otimes(\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}) and \lambda_{\max}((\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}})\otimes(\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}))=\lambda_{\max}(\Pi_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}})\lambda_{\max}(\Pi_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}) . Consider the fact of \lVert\overline{\Pi}_{\Sigma}f\rVert=\sqrt{1-\beta^{2}_{\Sigma}} with the range of \beta^{2}_{\Sigma} shown in eq. 11 and apply the operator \overline{\Pi}_{\Sigma}\Pi_{\mathcal{S}}\overline{\Pi}_{\Sigma} , then the supremum of \alpha_{\mathcal{S}} comes to \displaystyle\alpha_{\mathcal{S}} \displaystyle\leq\cos\Big(\cos^{-1}\sqrt{\lambda_{\max}\left(\overline{\Pi}_{\Lambda^{\prime}}\Pi_{\mathcal{V}^{\prime}}\overline{\Pi}_{\Lambda^{\prime}}\right)\lambda_{\max}\left(\overline{\Pi}_{\Omega^{\prime}}\Pi_{\mathcal{T}^{\prime}}\overline{\Pi}_{\Omega^{\prime}}\right)} \displaystyle\qquad\qquad\qquad-\cos^{-1}\Big(\sqrt{1-(\beta_{\Omega^{\prime}}^{\max}\beta^{\max}_{\Lambda^{\prime}})^{2}}\Big)\Big). Similarly, when we apply the operators \Pi_{\Sigma}\overline{\Pi}_{\mathcal{S}}\Pi_{\Sigma} and \overline{\Pi}_{\Sigma}\overline{\Pi}_{\mathcal{S}}\overline{\Pi}_{\Sigma} , other two inequalities are arrived at \displaystyle\begin{aligned} \alpha_{\mathcal{S}}\geq&\sin\Big(\cos^{-1}\sqrt{\lambda_{\max}\left(\Pi_{\Lambda^{\prime}}\overline{\Pi}_{\mathcal{V}^{\prime}}\Pi_{\Lambda^{\prime}}\right)\lambda_{\max}\left(\Pi_{\Omega^{\prime}}\overline{\Pi}_{\mathcal{T}^{\prime}}\Pi_{\Omega^{\prime}}\right)}\\ &\qquad\qquad-\cos^{-1}\left(\beta_{\Lambda^{\prime}}^{\min}\beta_{\Omega^{\prime}}^{\min}\right)\Big)\end{aligned} and \displaystyle\begin{aligned} \alpha_{\mathcal{S}}\geq&\sin\Big(\cos^{-1}\sqrt{\lambda_{\max}\left(\overline{\Pi}_{\Lambda^{\prime}}\overline{\Pi}_{\mathcal{V}^{\prime}}\overline{\Pi}_{\Lambda^{\prime}}\right)\lambda_{\max}\left(\overline{\Pi}_{\Omega^{\prime}}\overline{\Pi}_{\mathcal{T}^{\prime}}\overline{\Pi}_{\Omega^{\prime}}\right)}\\ &\qquad\qquad-\cos^{-1}\Big(\sqrt{1-\left(\beta_{\Lambda^{\prime}}^{\max}\beta^{\max}_{\Omega^{\prime}}\right)^{2}}\Big)\Big).\end{aligned} This completes the proof of 2 . Appendix D Proof of 3 In the forward direction, by repeatedly applying eq. 14 and eq. 15 , we obtain \displaystyle\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}f=\Pi_{\SF}\Pi_{\VT}f=\Pi_{\VT}\Pi_{\SF}f=\Pi_{\SF}f=f. Conversely, without loss of generality, suppose f is nonzero and \displaystyle\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}f=f. (47) Multiplying by \Pi_{\SF} and using \left(\Pi_{\SF}\right)^{2}=\Pi_{\SF} , we obtain \displaystyle\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}f=\Pi_{\SF}f. (48) By equating eq. 47 and eq. 48 , we have \displaystyle\ \Pi_{\SF}f=f indicating that f is perfectly localized in the spectral-frequency domain. Applying the Rayleigh-Ritz theorem [ 44 ] and the Hermitian property of \Pi_{\SF} (i.e., \left(\Pi_{\SF}\right)^{\ast}=\Pi_{\SF} ), we derive \displaystyle 1=\max_{f}\frac{f^{\ast}\Pi_{\SF}\Pi_{\VT}\Pi_{\SF}f}{f^{\ast}f}=\max_{f}\frac{f^{\ast}\Pi_{\VT}f}{f^{\ast}f}, which confirms eq. 14 , establishing perfect localization in the vertex-time domain. This completes the proof of 3 . Appendix E Proof of 4 Substituting the joint bandlimiting constraint within the objective function in eq. 18 , we obtain \displaystyle\begin{aligned} \xi_{i}=\argmax_{\xi_{i}}~&\lVert\Pi_{\VT}\Pi_{\Sigma}\xi_{i}\rVert\\ \ST&\lVert\xi_{i}\rVert=1,~\langle\xi_{i},\xi_{j}\rangle=0,~j\neq i.\end{aligned} (49) By applying the Rayleigh-Ritz theorem [ 44 ] , the solutions to eq. 49 are the eigenvectors of the operator (\Pi_{\VT}\Pi_{\Sigma})^{\ast}\Pi_{\VT}\Pi_{\Sigma}=\Pi_{\Sigma}\Pi_{\VT}\Pi_{\Sigma} , i.e., \Pi_{\Sigma}\Pi_{\VT}\Pi_{\Sigma}\xi_{i}=\lambda_{i}\xi_{i} , where \lambda_{i} are eigenvalues corresponding to the eigenvectors \xi_{i} [ 45 ] . Given that \Pi_{\Sigma}\xi_{i}=\xi_{i} and \left(\Pi_{\Sigma}\right)^{\ast}=\Pi_{\Sigma} , we have \displaystyle\begin{aligned} \lambda_{j}\delta_{ij}&=\langle\xi_{i},\Pi_{\Sigma}\Pi_{\VT}\Pi_{\Sigma}\xi_{j}\rangle\\ &=\langle\left(\Pi_{\Sigma}\right)^{\ast}\xi_{i},\Pi_{\VT}\Pi_{\Sigma}\xi_{j}\rangle=\langle\xi_{i},\Pi_{\VT}\xi_{j}\rangle.\end{aligned} (50) This completes the proof of 4 .