| Izvestiya: Mathematics |
|
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper) Maltsev equal-norm tight frames S. Ya. Novikov, V. V. Sevost'yanova Samara National Research University
Russian version:
Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, 2022, Volume 86, Issue 4, DOI: https://doi.org/10.4213/im9137 
Bibliographic databases:
    § 1. IntroductionLet $n$ and $d$ be integers, $n\geqslant d$. A frame in $\mathbb{R}^d$ is a complete family of $n$ vectors in $d$-dimensional Euclidean space, generalizing the concept of a basis by omitting the requirement of linear independence of all vectors. More precisely, a family of vectors $\{\varphi_j\}_{j=1}^n$ is called a frame of $\mathbb{R}^d$ if there are numbers $a,b$, $0<a\leqslant b< \infty$, such that for all $ \mathbf{x}\in \mathbb{R}^d$ we have
$$
\begin{equation*}
a\|\mathbf{x}\|^2\leqslant \sum_{j=1}^n|\langle \mathbf{x},\varphi_j\rangle |^2\leqslant b\|\mathbf{x}\|^2.
\end{equation*}
\notag
$$
The numbers $a$ and $b$ are referred to as frame bounds. They are not uniquely defined. Usually, they are understood as the optimal bounds, that is, the minimum $b$ and the maximum $a$. In finite-dimensional spaces, the concept of a frame is equivalent to that of a complete system, that is, $\operatorname{span}\{\varphi_j\}_{j=1}^n=\mathbb{R}^d$. This and other well-known facts about frames can be found in [1]. The synthesis operator for a finite system $\{\varphi_j\}_{j=1}^n$ of vectors in $\mathbb{R}^d$ is defined as $\mathbf{\Phi} \colon \mathbb{R}^n \to \mathbb{R}^d$, $\mathbf{\Phi} \mathbf{x} :=\sum_{j=1}^n \mathbf{x}(j)\varphi_j$, where $\mathbf{x}(j)$ denotes the $j$th coordinate of $\mathbf{x}\in \mathbb{R}^n$. The conjugate of the synthesis operator is the analysis operator $\mathbf{\Phi}^* \colon \mathbb{R}^d \to \mathbb{R}^n$, defined by $(\mathbf{\Phi}^*\mathbf{y})(j) = \langle \varphi_j,\mathbf{y}\rangle$ for $j = 1,\dots,n$. The composite $\mathbf{\Phi}^*\mathbf{\Phi}\colon\mathbb{R}^n\to \mathbb{R}^n$ of the analysis and synthesis operators determines the Gram matrix, that is, the $(n\times n)$-matrix whose $(j,j')$th entry is equal to $(\mathbf{\Phi}^*\mathbf{\Phi})(j,j') = \langle\varphi_j,\varphi_{j'}\rangle$. The composite $\mathbf{\Phi}\mathbf{\Phi}^* \colon \mathbb{R}^d\to \mathbb{R}^d$ in the inverse order is the frame operator $\mathbf{\Phi}\mathbf{\Phi}^*\mathbf{y} = \sum_{j=1}^n\langle\varphi_j,\mathbf{y}\rangle\varphi_j$. It is well known that sequences $\{\varphi_j\}_{j=1}^n$ and $\{\widehat{\varphi}_j\}_{j=1}^n$ in $\mathbb{R}^d$ have equal Gram matrices if and only if there is a unitary operator $\mathbf{U}$ such that $\mathbf{U}\varphi_j=\widehat{\varphi}_j$ for all $j = 1,\dots,n$. For a single vector $\{\varphi_j\}$, the synthesis and analysis operators take the form
$$
\begin{equation*}
\varphi_j\colon \mathbb{R}\to\mathbb{R}^d,\quad \varphi_j x = x\varphi_j;\qquad \varphi_j^*\colon \mathbb{R}^d\to\mathbb{R},\quad \varphi_j^*\mathbf{y} = \langle\varphi_j, \mathbf{y} \rangle.
\end{equation*}
\notag
$$
The frame operator may be written in this notation as $\mathbf{\Phi}\mathbf{\Phi}^*=\sum_{j=1}^n\varphi_j\varphi_j^*$. Hence the matrix representing the synthesis operator $\mathbf{\Phi}$ is the $(d\times n)$-matrix whose columns are the coordinates of the frame vectors $\{\varphi_j\}_{j=1}^n$. In particular, if the frame bounds are equal to each other, then the frame operator is represented by the diagonal matrix $\mathbf{\Phi}\mathbf{\Phi^*}{=}\, a\mathbf{I}_{\mathbb{R}^d}$ with $a>0$, and this formula gives a simple frame representation of vectors or signals:
$$
\begin{equation*}
\mathbf{x}=\frac 1a\mathbf{\Phi}\mathbf{\Phi^*}\mathbf{x} =\frac1{a}\sum_{j=1}^n\langle\varphi_j,\mathbf{x}\rangle\varphi_j, \qquad \mathbf{x}\in \mathbb{R}^d.
\end{equation*}
\notag
$$
These frames are said to be tight or $a$-tight, and $1$-tight frames are called Parseval frames. Tight frames all of whose vectors have equal norms are of particular interest. These frames are called equal-norm tight frames. In general, a frame $\{\varphi_j\}_{j=1}^n$ is said to be equal-norm if there is a $c>0$ such that $\|\varphi_{j}\|^2=c$, $j=1,\dots,n$. Given an equal-norm $a$-tight frame, we have a connection between $d$, $c$ and $a$:
$$
\begin{equation*}
da=\operatorname{trace}(a\,\mathbf{I}_{\mathbb{R}^d}) =\operatorname{trace}(\mathbf{\Phi}\mathbf{\Phi^*}) =\operatorname{trace}(\mathbf{\Phi^*}\mathbf{\Phi})= \sum_{j=1}^n\|\varphi_j\|^2=nc.
\end{equation*}
\notag
$$
In particular, $d=nc$ for Parseval frames. Hence equal-norm Parseval frames have norms $\leqslant 1$.
§ 2. Naimark’s theorem and its matrix consequencesThe following result of Naimark [2] turned out to be fundamental for numerical constructions of frames. It is repeatedly cited in the papers on frames and their applications. Theorem 1. If $\mathbf{\Phi}= \{\varphi_j\}_{j=1}^n$ is a Parseval frame in $\mathbb{R}^d$, then there is an orthonormal basis $\{\mathbf{b}_j\}_{j=1}^n$ in $\mathbb{R}^n$ such that $\varphi_j=\mathbf{P}_{\mathbb{R}^d} \mathbf{b}_j$ for all $j$, where $\mathbf{P}_{\mathbb{R}^d}$ is the orthogonal projection of $\mathbb{R}^n$ to $\mathbb{R}^d$. The converse also holds and is easily provable. Theorem 2. If $\{\mathbf{b}_j\}_{j=1}^n$ is an orthonormal basis in $\mathbb{R}^n$, then $\mathbf{\Phi}= \{\mathbf{P}_{\mathbb{R}^d} \mathbf{b}_j\}_{j=1}^n$ is a Parseval frame in $\mathbb{R}^d$, where $\mathbf{P}_{\mathbb{R}^d}$ is the orthogonal projection of $\mathbb{R}^n$ to $\mathbb{R}^d$. Proof. If $\varphi_j=\mathbf{P}_{\mathbb{R}^d} \mathbf{b}_j$, $j=1,\dots, n,$ and $\mathbf{x}\in \mathbb{R}^d$, then
$$
\begin{equation*}
\|\mathbf{x}\|^2=\|\mathbf{P}_{\mathbb{R}^d} \mathbf{x}\|^2=\sum_{j=1}^n|\langle \mathbf{P}_{\mathbb{R}^d} \mathbf{x},\mathbf{b}_j\rangle |^2 =\sum_{j=1}^n|\langle \mathbf{x},\mathbf{P}_{\mathbb{R}^d}\mathbf{b}_j\rangle|^2 =\sum_{j=1}^n|\langle \mathbf{x},\varphi_j\rangle |^2.
\end{equation*}
\notag
$$
Hence $\mathbf{\Phi}$ is a Parseval frame. $\Box$ Theorems 1 and 2 were extended in [3] to frames of general form, which turned out to be projections of Riesz bases. Projections of general orthogonal systems (not necessarily complete) were considered in [4]. Let be the matrix of the synthesis operator, that is, the $(d\times n)$-matrix whose columns are the coordinates of the frame vectors $\{\varphi_j\}_{j=1}^n$ in the canonical basis.Theorem 3. Let $\{\varphi_j\}_{j=1}^n$ be a frame in $\mathbb{R}^d$. Then the coordinates of the vectors $\varphi_j$ may be regarded as the first $d$ coordinates of some vectors in $\mathbb{R}^n$ which form a basis in $\mathbb{R}^n$. If $\{\varphi_j\}_{j=1}^n$ is a tight frame, then the coordinates of the vectors $\varphi_j$ are the first $d$ coordinates of some vectors which form an orthogonal basis in $\mathbb{R}^n$. Proof. Let $\{\varphi_j\}_{j=1}^n$ be an arbitrary frame in $\mathbb{R}^d$. The analysis operator $\Phi^*\colon \mathbb{R}^d\to \mathbb{R}^n$ has matrix
If $\Phi^*\mathbf{x}=\mathbf{0}$, then
$$
\begin{equation*}
0=\|\Phi^*\mathbf{x}\|^2=\sum_{j=1}^n|\langle \varphi_j,\mathbf{x}\rangle |^2.
\end{equation*}
\notag
$$
Since $\operatorname{span}\{\varphi_j\}_{j=1}^n=\mathbb{R}^d$, we have $\mathbf{x}=\mathbf{0}$. Hence, $\Phi^*$ is an injective mapping. We can therefore extend $\Phi^*$ to a bijection $\widetilde{\Phi}^*\colon \mathbb{R}^n\to \mathbb{R}^n$, for example, in the following way. Let $\{\mathbf{e}_j\}_{j=1}^n$ be the canonical basis in $\mathbb{R}^n$. Then we choose a basis $\{\mathbf{b}_j\}_{j=d+1}^n$ for the orthogonal complement of the range $\mathcal{R}_{\Phi^*}$ in $\mathbb{R}^n$ and set by definition $\widetilde{\Phi}^*\mathbf{e}_j:=\mathbf{b}_j$, $j= d+1,\dots, n$. The matrix $\widetilde{\Phi}^*$ is an $(n\times n)$-matrix whose first $d$ columns coincide with the matrix $\Phi^*$:
Since $\widetilde{\Phi}^*$ is surjective by construction, the columns of this matrix are complete in $\mathbb{R}^n$. Hence the rows of the matrix $\widetilde{\Phi}^*$ are complete in $\mathbb{R}^n$, that is, they are linearly independent and constitute a basis for $\mathbb{R}^n$. If $\{\varphi_j\}_{j=1}^n$ is an $a$-tight frame for $\mathbb{R}^d$, then, as noted above, $\Phi\Phi^*{=}\,a I$. Hence the rows of the matrix of $\Phi$ are orthogonal vectors in $\mathbb{R}^n$. By adding $n\,{-}\,d$ rows to this matrix in such a way that the extended matrix has orthogonal rows, we obtain an $(n\,{\times}\,n)$-matrix with orthogonal rows. Hence the columns of the extended matrix are also orthogonal. $\Box$ § 3. Maltsev’s matrices. Equiangular frames. Full-spark framesMaltsev published the paper [5] in 1947. He answered a question in [6] by constructing a matrix with orthogonal rows of unit length and columns of equal length. We call such matrices Maltsev’s matrices. In fact it was the first construction of an equal-norm Parseval frame. While Naimark’s paper mentioned in § 2 is frequently cited in the literature about frames, Maltsev’s note went unnoticed. Modern constructions of equal-norm tight frames for $\mathbb{R}^d$ appeared only at the beginning of the 21st century [7]. Consider the construction of Maltsev’s matrices in more detail. We first justify the possibility of considering only the case when $d<n/2$. Lemma 1. Suppose that $\{\varphi_j\}_{j=1}^{n}$ is an $a$-tight frame for $\mathbb{R}^d$ and $d<n$. Then the $(n\times n)$-matrix $(1/a)\mathbf{\Phi}^* \mathbf{\Phi}$ is the matrix of orthogonal projection to a $d$-dimensional subspace of $\mathbb{R}^n$. The Gram matrix $\mathbf{\Phi}^* \mathbf{\Phi}$ has eigenvalues $a$ of multiplicity $d$ and $0$ of multiplicity $n-d$. Proof. Since $\{\varphi_j\}_{j=1}^{n}$ is an $a$-tight frame, we have
$$
\begin{equation*}
\varphi_l=\frac{1}{a}\sum_{j=1}^n\langle\varphi_j, \varphi_l\rangle\varphi_j, \qquad l=1,\dots, n.
\end{equation*}
\notag
$$
Hence, for any $k$, $l$ we obtain or
If $\mathbf{P}:=(1/a)\mathbf{\Phi}^* \mathbf{\Phi}$, then $\mathbf{P}=\mathbf{P}^2$. Since $\mathbf{P}$ is self-adjoint, we see that $\mathbf{P}$ is the orthogonal projection to a $d$-dimensional subspace. The matrix of this orthogonal projection has $d$ eigenvalues equal to $1$, and $n-d$ zero eigenvalues, $\operatorname{trace} \mathbf{P} =\operatorname{rank} \mathbf{P} = d$. Hence $\mathbf{\Phi}^* \mathbf{\Phi}= a\mathbf{P}$ has $d$ eigenvalues equal to $a$, and $n-d$ zero eigenvalues, Theorem 4. Every $a$-tight frame $\{\varphi_j\}_{j=1}^{n}$ for $\mathbb{R}^d$ has a Naimark complement frame $\{\psi_j\}_{j=1}^{n}$ with the following properties: (i) $\{\psi_j\}_{j=1}^{n}$ is an $a$-tight frame for $\mathbb{R}^{(n-d)}$; (ii) the Gram matrix $\mathbf{\Psi}^* \mathbf{\Psi}=a \mathbf{I}_{\mathbb{R}^n} - \mathbf{\Phi}^* \mathbf{\Phi}$; (iii) $\mathbf{\Phi}\mathbf{\Psi}^*=\mathbf{0}$. Proof. (i) A direct verification shows that the matrix $\mathbf{Q}:=\mathbf{I}_{\mathbb{R}^n}-(1/a)\mathbf{\Phi}^*\mathbf{\Phi}$ satisfies the equality $\mathbf{Q}=\mathbf{Q}^*=\mathbf{Q}^2,$ and its eigenvalues are $1$ and $0$ with multiplicities $n-d$ and $d$ respectively. Hence the columns $\widetilde{\psi}_j:=\mathbf{Q}\mathbf{e}_j$, $j=1,\dots, n$, of the matrix $\mathbf{Q}$, where $\{\mathbf{e}_j\}_{j=1}^{n}$ is an orthonormal basis for $\mathbb{R}^n$, determine $\operatorname{span}\bigl(\{\widetilde{\psi}_j\}_{j=1}^{n}\bigr)=\mathbb{R}^{(n-d)}$.
If $\mathbf{f}\in \operatorname{span}\bigl(\{\widetilde{\psi}_j\}_{j=1}^{n}\bigr)$, then $\mathbf{Q}\mathbf{f}=\mathbf{f}$,
$$
\begin{equation*}
\mathbf{f}=\mathbf{Q}\biggl(\sum_{j=1}^n\langle\mathbf{Q} \mathbf{f}, \mathbf{e}_j\rangle \mathbf{e}_j\biggr)=\sum_{j=1}^n\langle \mathbf{f}, \mathbf{Q}\mathbf{e}_j\rangle \mathbf{Q} \mathbf{e}_j=\sum_{j=1}^n\langle \mathbf{f}, \widetilde{\psi}_j\rangle \widetilde{\psi}_j,
\end{equation*}
\notag
$$
that is, the system of vectors $\{\widetilde{\psi}_j\}_{j=1}^{n}$ is a Parseval frame for $\operatorname{span}\bigl(\{\widetilde{\psi}_j\}_{j=1}^{n}\bigr)$.
(ii) The vectors $\psi_j= \sqrt{a} \widetilde{\psi}_j$, $j=1,\dots, n$, form an $a$-tight frame for the space $\operatorname{span}(\{\psi_j\}_{j=1}^{n}) =\operatorname{span}\bigl(\{\widetilde{\psi}_j\}_{j=1}^{n}\bigr)$ and $\mathbf{\Psi}^*\mathbf{\Psi}=a\mathbf{I}_{\mathbb{R}^n}-\mathbf{\Phi}^*\mathbf{\Phi}$. (iii) By the lemma, we have
$$
\begin{equation*}
(\mathbf{\Psi}\mathbf{\Phi}^*)^*(\mathbf{\Psi}\mathbf{\Phi}^*) =\mathbf{\Phi}\mathbf{\Psi}^*\mathbf{\Psi}\mathbf{\Phi}^* =\mathbf{\Phi}(a\mathbf{I}-\mathbf{\Phi}^*\mathbf{\Phi})\mathbf{\Phi}^* =a\mathbf{\Phi}\mathbf{\Phi}^*-(\mathbf{\Phi}\mathbf{\Phi}^*)^2=\mathbf{0}.
\end{equation*}
\notag
$$
The Frobenius norm of the matrix Hence $\mathbf{\Psi}\mathbf{\Phi}^*=\mathbf{0}$, and its adjoint is $\mathbf{\Phi}\mathbf{\Psi}^*=\mathbf{0}$. $\Box$ Theorem 4 asserts that we can add $n-d$ rows to the $(d\times n)$-matrix $\mathbf{\Phi}$ of the synthesis operator for an equal-norm tight frame of vectors in $\mathbb{R}^d$ in such a way that the extended $(n\times n)$-matrix is orthogonal. Moreover, the added rows form the $((n-d)\times n)$-matrix of the synthesis operator $\mathbf{\Psi}$ for an equal-norm tight frame for the space $\mathbb{R}^{(n-d)}$. When $d=n/2$, we can take for $\mathbf{\Phi}$ two orthogonal $(d\times d)$-matrices multiplied by $1/\sqrt{2}$ and placed side by side. Consider Maltsev’s design for $d<n/2$. For completeness, we recall a construction (following [5]) of Sylvester–Walsh matrices, which form a subset of Hadamard matrices. Remark 1. For every positive integer $m$ there is a $(2^m\times 2^m)$-matrix $\mathbf{H}_{2^m}$ with entries $\pm 1$ and with mutually orthogonal rows and columns. Indeed, for $m=1$ we have a matrix
$$
\begin{equation*}
\mathbf{H}_2= \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}.
\end{equation*}
\notag
$$
We define higher-order matrices by putting
$$
\begin{equation*}
\mathbf{H}_{2^m}=\left( \begin{array}{c|c}
\rule{0pt}{14pt}\mathbf{H}_{2^{m-1}}&\mathbf{H}_{2^{m-1}}\\
\hline
\rule{0pt}{14pt}\mathbf{H}_{2^{m-1}}&-\mathbf{H}_{2^{m-1}}\\
\end{array}\right)=\mathbf{H}_2\otimes \mathbf{H}_{2^{m-1}},
\end{equation*}
\notag
$$
$2\leqslant m\in \mathbb{N}$, where $\otimes$ denotes the Kronecker product. The Sylvester–Walsh matrices are closely connected with discrete Walsh functions, which have many useful applications [8]. By the remark, for any positive integers $m$ and $k\leqslant 2^m$ there are $k$ mutually orthogonal rows of length $2^m$ with entries $\pm 1$. The number $n$ of columns of the required matrix $\mathbf{\Phi}$ is represented by
$$
\begin{equation*}
n= 2^{m_1}+\dots + 2^{m_t},\qquad 0\leqslant m_1<\dots< m_t.
\end{equation*}
\notag
$$
There is a number $s$ such that $1\leqslant s\leqslant t-1$ and $2^{m_s}< d\leqslant 2^{m_{s+1}}$. We construct the matrix $\mathbf{\Phi}$ of the synthesis operator for an equal-norm tight frame in two steps. At the first step we obtain a matrix with orthogonal rows and with entries $\pm 1$ and $0$. At the second step we normalize it without losing the orthogonality. The matrix of the first step is as follows: All non-zero blocks are filled with $\pm 1$. The block $A_{1,1}$ is a $(2^{m_1}\times 2^{m_1})$-matrix with orthogonal rows, the block $A_{2,2}$ is a $((2^{m_2}-2^{m_1})\times 2^{m_2})$-matrix with orthogonal rows, $\dots$, the block $A_{s,s}$ is a $((2^{m_s}- 2^{m_{s-1}})\times 2^{m_s})$-matrix with orthogonal rows. Thus the left part of $\mathbf{\Phi}$ consists of $2^{m_s}$ rows and $2^{m_1}+\dots + 2^{m_s}$ columns. All blocks with second subscript $s+1$ consist of $p:= 2^{m_{s+1}}+\dots + 2^{m_t}$ columns. The number of rows in any block $A_{i,s+1}$, $i=1, \dots, s$, is equal to that of $A_{i,i}$, $i=1, \dots, s$, and the block $A_{s+1,s+1}$ consists of $d-2^{m_s}$ rows and $p$ columns. Each block $A_{i,i}$, $i=1, \dots, s$, contains $2^{m_i}-2^{m_{i-1}}\leqslant 2^{m_i}$ orthogonal rows of length $2^{m_i}$. The existence of such rows is ensured by the remark. We take a closer look at the right side of the matrix. Split the block into $t-s$ blocks $B_j$ of size $d\times 2^{m_j}$, $j=s+1,\dots,t$. Each block $B_j$ has $d\leqslant 2^{m_j}$ rows. Hence the blocks $B_j$ can be filled by $\pm1$ in such a way that the rows of length $2^{m_j}$ are mutually orthogonal. We obtain orthogonal rows of length $p$ by combining the rows of the blocks $B_j$. This yields a $(d\times n)$-matrix with entries $\pm 1$ and $0$ and with mutually orthogonal rows.We proceed to normalize the entries of this matrix. All entries of the blocks $A_{i,i}$, $i=1,\dots,s$, are multiplied by $\alpha_i$, $i=1,\dots,s$, and all entries of the blocks $A_{j,s+1}$, $j=1,\dots,s+1$, are multiplied by $\beta_j$, $j=1,\dots,s+1$, in order to make the length of any row equal to $1$ and the length of any column equal to $\sqrt{d/n}$. The rows of the matrix remain orthogonal when we multiply the rows by any numbers. To specify the numbers $\alpha_i$ and $\beta_j$, we calculate the sums of squares of the entries in each column of $\Phi$:
$$
\begin{equation}
\alpha_1^2\cdot2^{m_1}=\frac{d}{n},\quad \alpha_2^2\cdot(2^{m_2}-2^{m_1})=\frac{d}{n},\quad \dots,\quad \alpha_s^2\cdot(2^{m_s}-2^{m_{s-1}})=\frac{d}{n},
\end{equation}
\tag{3.1}
$$
$$
\begin{equation}
\beta_1^2\cdot2^{m_1}+\beta_2^2\cdot(2^{m_2}-2^{m_1})+\dots+ \beta_s^2\cdot(2^{m_s}-2^{m_{s-1}})+ \beta_{s+1}^2\cdot(d-2^{m_{s}})=\frac{d}{n}.
\end{equation}
\tag{3.2}
$$
Using (3.1), we obtain the values
$$
\begin{equation*}
\alpha_1^2=\frac{d}{n\cdot2^{m_1}},\qquad \alpha_i^2=\frac{d}{n\cdot(2^{m_i}-2^{m_{i-1}})},\quad i=2,\dots,s.
\end{equation*}
\notag
$$
By the condition of normalization of rows,
$$
\begin{equation}
\begin{aligned} \, &\alpha_1^2\cdot2^{m_1}+\beta_1^2\cdot(2^{m_{s+1}}+\dots+2^{m_t})=1, \\ &\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots \\ &\alpha_s^2\cdot2^{m_s}+\beta_s^2\cdot(2^{m_{s+1}}+\dots+2^{m_t})=1, \\ &\beta_{s+1}^2\cdot(2^{m_{s+1}}+\dots+2^{m_t})=1. \end{aligned}
\end{equation}
\tag{3.3}
$$
Substituting the known values of $\alpha_i^2$ in (3.3), we have
$$
\begin{equation}
\begin{aligned} \, \beta_1^2 &=\frac{1}{2^{m_{s+1}}+\dots+2^{m_t}}\biggl(1-\frac{d}{n}\biggr), \\ \beta_j^2 &=\frac{1}{2^{m_{s+1}}+\dots+2^{m_t}} \biggl(1-\frac{d\cdot2^{m_j}}{n(2^{m_j}-2^{m_{j-1}})}\biggr),\qquad j=2,\dots,s, \\ \beta_{s+1}^2 &=\frac{1}{2^{m_{s+1}}+ \dots+2^{m_t}}. \end{aligned}
\end{equation}
\tag{3.4}
$$
It follows from the inequality $d<n/2$ that
$$
\begin{equation*}
\begin{aligned} \, &1-\frac{d\cdot2^{m_j}}{n(2^{m_j}-2^{m_{j-1}})}> 1-\frac{\frac{n}{2}\cdot2^{m_j}}{n(2^{m_j}-2^{m_{j-1}})} \\ &\qquad=\frac{(2^{m_j}-2^{m_{j-1}})-2^{m_j-1}}{2^{m_j}-2^{m_{j-1}}} =\frac{2^{m_j-1}-2^{m_{j-1}}}{2^{m_j}-2^{m_{j-1}}}\geqslant0. \end{aligned}
\end{equation*}
\notag
$$
Hence the right-hand sides of the equalities (3.4) are positive. This guarantees the existence of the numbers $\beta_j$. The resulting numbers $\alpha_i$ and $\beta_j$ satisfy the equality (3.2). The systems of vectors thus obtained will be called Maltsev equal-norm tight frames. We now consider examples. Example. Consider the case when $d=3$, $n=7$. The number $n$ is represented as $n=2^0+2^1+2^2$. Then the synthesis matrix is We find the values of $\alpha_i$ and $\beta_j$ from the normalization conditions: Example. Consider the case when $d=7$, $n=15$. Since $15=2^0+2^1+2^2+2^3$, we obtain where Example. Here is a Hadamard matrix of order $16$ constructed by Maltsev’s algorithm: We recall that an equal-norm frame $\{\varphi_j\}_{j=1}^n$ is said to be equiangular if there is a number $\gamma\geqslant 0$ such that $|\langle\varphi_{j},\varphi_{j^{'}}\rangle|=\gamma$ for all $j\neq j'$. The matrix formed by the rows $1$, $9$, $5$, $3$, $2$, $16$ of the matrix (3.5) is the synthesis matrix of an equiangular frame. Another way of obtaining an equiangular tight frame was given in [9]. It uses the rows with numbers $2$, $3$, $4$, $6$, $11$, $16$. We do not know whether other choices of rows can give an equiangular frame. Maltsev frames for $n\neq 2^k$ cannot be equiangular because the columns in the left part of the matrix are orthogonal to each other while those in the right part form at least one non-orthogonal pair. In the literature on sparse representations, much attention is paid to the spark of the system (see [10]). Definition 1. The spark of a $(d\times n)$-matrix $\mathbf{\Phi}$ is the minimal number of linearly dependent columns of $\mathbf{\Phi}$. If $\operatorname{spark}(\Phi)=d+1$, then any subset of $d$ columns consists of linearly independent vectors. In this case, the system is called a full-spark frame. Proposition 1. There are $4$ linearly dependent vectors in any Maltsev equal-norm tight frame of $n\geqslant 4$ vectors. Proof. If $\{\varphi_i\}_{i=1}^n$ is a Maltsev tight frame with $n\geqslant4$, then the binary representation of $n$ contains powers $2^t$ with $t\geqslant2$. Let $t$ be the maximal number such that $2^t\leqslant n$. Then the last block $B_t$ of the $(d\times n)$-matrix $\Phi$ is of size $d\times 2^t$. We claim that there are $4$ linearly dependent columns in the block $B_t.$
Indeed, relabel the frame vectors in such a way that $\varphi_1,\dots,\varphi_{2^t}$ are the last $2^t$ columns of the matrix $\Phi$ (hence they form the block $B_t$). By the construction of Maltsev frames, $B_t$ is obtained by deleting any $2^t-d$ rows from the matrix
$$
\begin{equation*}
\mathbf{H}_{2^t}=\left( \begin{array}{c|c} \rule{0pt}{14pt}\mathbf{H}_{2^{t-1}}&\mathbf{H}_{2^{t-1}}\\ \hline \rule{0pt}{14pt}\mathbf{H}_{2^{t-1}}&-\mathbf{H}_{2^{t-1}} \end{array}\right).
\end{equation*}
\notag
$$
Let $B$ (resp. $B'$) be the result of deleting $2^{t-1}-p$ rows (resp. $2^{t-1}-d+p$ rows) from the matrix $\mathbf{O}_{t-1}$. Then the size of $B$ is $p\times2^{t-1}$, the size of $B'$ is $(d-p)\times2^{t-1}$ and we have
$$
\begin{equation*}
B_t=\left( \begin{array}{c|c} \rule{0pt}{14pt}B & B\\ \hline \rule{0pt}{14pt}B' & -B' \end{array}\right).
\end{equation*}
\notag
$$
For every $i=1,\dots,2^{t-1}$, the sum of the columns of the block $B_t$ with numbers $i$ and $k_i=2^{t-1}+i$ is equal to
$$
\begin{equation*}
\varphi_{i}+\varphi_{k_i}= \left(\begin{array}{c} 2\beta_1\\ \dots\\ 2\beta_p\\0\\ \dots\\0\\ \end{array}\right) \begin{array}{l} \hspace{-6pt}\left.\begin{array}{c} \\\\\\ \end{array}\right\}p\\ \hspace{-6pt}\left.\begin{array}{c} \\\\\\ \end{array}\right\}d-p \end{array},
\end{equation*}
\notag
$$
where the numbers $\beta_j$ are those corresponding to the rows of the block $B_t$ in the construction of the Maltsev frame. Hence for any $i$, $j$ we have Since the block $B_t$ has at least four columns, we conclude that among the frame vectors there are four linearly dependent vectors. $\Box$ Hence Maltsev tight frames can be full-spark only when $\operatorname{spark}(\Phi)=d+1\leqslant4$. Let $\{\varphi_i\}_{i=1}^n$ be a full-spark Maltsev tight frame. We have seen that $d\leqslant3$. Since multiplication of the blocks $A_{i,j}$ by the non-zero numbers $\alpha_i$ and $\beta_j$ in the construction of $\Phi$ preserves the orthogonality of rows and the linear dependence or independence of columns, we can assume that all non-zero entries of the matrix $\Phi$ are equal to $\pm1$. To find the possible sizes of the block $B_t$, we can always multiply the rows and columns of $\Phi$ by $\pm 1$ in such a way that all the entries in the first row and the first column of $B_t$ are equal to $1$. Suppose that $d=2$ and $B_t$ has more than two columns. Since $\varphi_1=\begin{pmatrix}1\\ 1\\\end{pmatrix}$ and the first coordinates of $\varphi_2$ and $\varphi_3$ are equal to 1, we obtain two equal vectors in the frame for any choice of the second coordinates. This contradicts the equality $\operatorname{spark}(\Phi)=3$. Hence a full-spark Maltsev frame for $\mathbb{R}^2$ is possible only for $n=3$. This frame is uniquely determined by the algorithm above: When $d=3$, a simple search yields a unique choice for the block $B_t$ (up to permutation of columns):
$$
\begin{equation*}
B_t=\left(\begin{array}{cccc} 1&1&1&1\\ 1&1&-1&-1\\ 1&-1&-1&1\\ \end{array}\right).
\end{equation*}
\notag
$$
Thus we obtain the following restrictions on the number of columns in $B_t$ and the number of vectors in the frame: $n\leqslant2^0+2^1+2^2=7$. Putting $n=5,6,7$, we see that none of the Maltsev frames is full-spark. Hence the matrix $B_2$ gives the unique possible full-spark Maltsev frame for $\mathbb{R}^3$.
Citation in format AMSBIB
\Bibitem{NovSev22} |
|
||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|