On spectrally optimal duals for r r -erasures of frames generated by graphs
Deepshikha, Aniruddha Samanta · 2025
Read On spectrally optimal duals for r r -erasures of frames generated by graphs by Deepshikha, Aniruddha Samanta (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-20347.txt.
Introduction
Deepshikha and Aniruddha Samanta wrote a 2025 math paper on backup representations that survive losing several pieces of data. A frame is a redundant set of vectors for encoding signals, and a dual frame does the decoding. When some coefficients are erased, a good dual keeps the error small. The authors study duals that are spectrally optimal, minimizing the worst case error, for frames built from graphs.
Extending earlier work on one and two erasures, they treat any number of erasures. For frames from a connected graph, the standard canonical dual is the unique best choice. For disconnected graphs, the canonical dual is still optimal but shares the crown with others. Unitary copies of a frame share the same error behavior with their canonical duals.
Catalog record
| CREATOR | Deepshikha, Aniruddha Samanta |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-20347
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On spectrally optimal duals for r r -erasures of frames generated by graphs Deepshikha, Aniruddha Samanta Abstract In [ 9 ] , authors studied spectrally optimal dual frames for 1 1 -erasure and 2 2 -erasures of frames generated by graph. In this paper, we study spectrally optimal dual frames for r r -erasures. We show that the spectral radius of the error operator of unitary equivalent frames is same with respect to their respective canonical dual frames. We prove that if a frame is generated by a connected graph, then its canonical dual frame is the unique spectrally optimal dual frame for r r -erasures. Further, we show that the canonical dual of frames generated by disconnected graphs are non-unique spectrally optimal dual frames for r r -erasures. AMS Subject Classification(2010): 05C40, 05C50, 42C15, 42C40, 46C05. Keywords. Frames generated by graphs, Dual frames, Spectrally optimal dual frames, Laplacian matrix, Error operator. 1 Introduction In order to solve certain complex problems in the non-harmonic Fourier series, Duffin and Schaeffer [ 11 ] developed the idea of frames. Frames are redundant sequences of vectors that span a vector space. The redundancy of frames makes them very useful in many applications, including data and image processing, signal transmission, image segmentation, coding theory, etc. Due to redundancy, the data transmitted using frames can be reconstructed with minimal error if erasures occur during the transmission. Finite frames are widely used in frame theory due to their significant relevance in applications. In [ 7 ] , authors introduced a new class of finite frames using simple graphs and called them frames generated by graphs. They established some graph properties using frame properties and vice-versa. Consequently, it provides a beautiful connection between the three classical branches of mathematics, namely, frame theory, graph theory, and matrix theory. Further, frames generated by graphs have some special properties, and some of them are stated in the preliminaries section of this article. The problem of erasures commonly occurs due to transmission losses or disturbances during transmission. The problem of erasures can be handled in two ways. One way is to find a frame that can minimize the maximal error in reconstruction. Another way is to find an optimal dual frame for a pre-selected frame in order to minimize the maximal error of reconstruction. In this paper, we focus on the second approach. A dual frame of a pre-selected frame that minimizes the maximal error of reconstruction is called an optimal dual frame. Various measurements are used to measure the error operator. If operator norm is used, then we use the term optimal dual frame. If the spectral radius is used to measure the error operator, then dual frames that minimize the maximum error are called spectrally optimal dual frames (or, in short, SOD -frames). In [ 8 ] , authors studied optimal dual frames of frames generated by graphs. Spectrally optimal dual frames for 1 -erasure and 2 -erasures of frames generated by graphs is studied in [ 9 ] . In this paper, we study the spectrally optimal dualS for r erasures of frames generated by graphs. The outline of this paper is as follows. In Section 2, we provide the basic definitions and results of frame theory, spectrally optimal dual frames, spectral graph theory, frames generated by graphs and SOD -frame for 1 -erasure and 2 -erasures required in the rest of the article. In Section 3, we study spectrally optimal dual frames for r -erasures of frames generated by graphs.We show that the spectral radius of the error operator of unitary equivalent frames is same with respect to their respective canonical dual frames. We prove that if \Phi=\{\phi_{i}\}_{i\in[n]} is an L_{G}(n,n-k) -frame with frame operator S_{\Phi} , then \rho^{(r)}_{\Phi,S^{-1}_{\Phi}\Phi}=1 for any r\in[n]\setminus\{1\} . We prove that if a frame is generated by a connected graph, then its canonical dual frame is the unique spectrally optimal dual frame for r -erasures. Further, we show that the canonical dual of frames generated by disconnected graphs are non-unique spectrally optimal dual frames for r -erasures.. 2 Preliminaries Throughout the rest of the article, we consider finite frames and \mathbb{C}^{k} is a k -dimensional Hilbert space. We use the notation [n] to denote the set \{1,2,\ldots,n\} and M=[m_{i,j}]_{i\in[p],j\in[q]} to denote the matrix M of order p\times q where m_{i,j} is the (i,j) -th entry of M . Also, diag(\alpha_{1},\alpha_{2},\ldots,\alpha_{n}) denotes the diagonal matrix of order n with respective diagonal entries \alpha_{1},\alpha_{2},\ldots,\alpha_{n} . A sequence of vectors \Phi:=\{\phi_{i}\}_{i\in[n]} in \mathbb{C}^{k} is called a frame for \mathbb{C}^{k} if there exist constants 0<A_{o}\leq B_{o} such that for any f\in\mathbb{C}^{k} , we have \displaystyle A_{o}\|f\|^{2}\leq\sum_{i\in[n]}|\langle f,\phi_{i}\rangle|^{2}\leq B_{o}\|f\|^{2}. The constants A_{o} and B_{o} are called the lower and upper frame bounds of \Phi , respectively. For a frame \Phi=\{\phi_{i}\}_{i\in[n]} , the analysis operator T_{\Phi}:\mathbb{C}^{k}\rightarrow\mathbb{C}^{n} is defined as T_{\Phi}(f)=\{\langle f,\phi_{i}\rangle\}_{i\in[n]} . The analysis operator T_{\Phi} is linear and bounded. The adjoint of T_{\Phi} , T^{*}_{\Phi}:\mathbb{C}^{n}\rightarrow\mathbb{C}^{k} , is called a synthesis operator and defined by T_{\Phi}(\{\alpha_{i}\}_{i\in[n]})=\sum\limits_{i\in[n]}\alpha_{i}\phi_{i} . The canonical matrix representation of the synthesis operator is a k\times n matrix such that its i^{\text{th}} column is the vector \phi_{i} that is [T^{*}_{\Phi}]=[\phi_{1}\,\,\phi_{2}\,\,\cdots\,\,\phi_{n}] . The frame operator S_{\Phi}:\mathbb{C}^{k}\rightarrow\mathbb{C}^{k} is the composition of the synthesis operator and analysis operator such that S_{\Phi}(f)=\sum\limits_{i\in[n]}\langle f,\phi_{i}\rangle\phi_{i} . The operator S_{\Phi} is bounded, linear, self-adjoint, positive, and invertible. The composition T_{\Phi}T_{\Phi}^{*}:\mathbb{C}^{n}\rightarrow\mathbb{C}^{n} is called the Gramian operator of \Phi . The canonical matrix representation of the Gramian operator is said to be the Gramian matrix , defined by \mathcal{G}_{\Phi}=[\langle\phi_{j},\phi_{i}\rangle]_{i,j\in[n]} where \langle\phi_{j},\phi_{i}\rangle is the (i,j) -th entry of \mathcal{G}_{\Phi} . A frame \Psi=\{\psi_{i}\}_{i\in[n]} of \mathbb{C}^{k} is called a dual frame of \Phi if for any f\in\mathbb{C}^{k} , f=\sum\limits_{i\in[n]}\langle f,\phi_{i}\rangle\psi_{i}=\sum\limits_{i\in[n]}\langle f,\psi_{i}\rangle\phi_{i} . The sequence \{S_{\Phi}^{-1}\phi_{i}\}_{i\in[n]} is a also a dual frame of \Phi and it is called the canonical dual frame of \Phi . We denote the set of all dual frames of a frame \Phi by D_{\Phi} . The dual frames which are not canonical dual are called alternate dual frames . If \Psi=\{\psi_{i}\}_{i\in[n]}\in D_{\Phi} then there exist a sequence \{\mu_{i}\}_{i\in[n]}\subset\mathbb{C}^{k} such that \psi_{i}=S_{\Phi}^{-1}\phi_{i}+\mu_{i} for i\in[n] and \sum\limits_{i\in[n]}\langle f,\mu_{i}\rangle\phi_{i}=0 for all f\in\mathbb{C}^{k} . We say two frames \Phi_{1}=\{\phi_{1,i}\}_{i\in[n]} and \Phi_{2}=\{\phi_{2,i}\}_{i\in[n]} are unitary equivalent if there exists a unitary operator V:\mathbb{C}^{k}\rightarrow\mathbb{C}^{k} such that V(\phi_{1,i})=\psi_{1,i} for all i\in[n] . Refer to [ 3 , 4 , 5 , 6 ] for the general theory of frames and its applications. Suppose \Phi=\{\phi_{i}\}_{i\in[n]} is a frame for \mathbb{C}^{k} and \Psi=\{\psi_{i}\}_{i\in[n]} is a dual frame of \Phi . Then for \Lambda\subset[n] , the error operator E_{\Phi,\Psi,\Lambda}:\mathbb{C}^{k}\rightarrow\mathbb{C}^{k} is defined by \displaystyle E_{\Phi,\Psi,\Lambda}(f)=\sum_{i\in\Lambda}\langle f,\phi_{i}\rangle\psi_{i}. For 1\leq r<n , let \rho^{(r)}_{\Phi,\Psi}:=\max\{\rho(E_{\Phi,\Psi,\Lambda}):\Lambda\subset[n]\text{ and }|\Lambda|=r\} , where \rho(E_{\Phi,\Psi,\Lambda}) is the spectral radius of E_{\Phi,\Psi,\Lambda} . A dual frame \Psi of the frame \Phi is called a spectrally optimal dual frame (or simply SOD -frame ) for 1 -erasure if \rho^{(1)}_{\Phi}:=\min\left\{\rho^{(1)}_{\Phi,\widetilde{\Psi}}:\widetilde{\Psi}\in D_{\Phi}\right\}=\rho^{(1)}_{\Phi,\Psi} . Spectrally optimal dual frames for r -erasures are defined inductively. For 1<r<n , a dual frame \Psi=\{\psi_{i}\}_{i\in[n]} of a frame \Phi=\{\phi_{i}\}_{i\in[n]} is called spectrally optimal dual frame for r -erasures if \Psi is an spectrally optimal dual frame for (r-1) -erasures and \rho^{(r)}_{\Phi}:=\min\{\rho^{(r)}_{\Phi,\widetilde{\Psi}}:\widetilde{\Psi}\in D_{\Phi}\}=\rho^{(r)}_{\Phi,\Psi} . We denote the set of all SOD -frame of \Phi for r -erasures by SOD_{\Phi}^{r} . Remark 2.1 .