Constrained Low Rank Approximation of the Hermitian Nonnegative-Definite Matrix

Haixia Chang

School of Statistics and Mathematics, Shanghai Lixin University of Accounting and Finance, Shanghai, China.

DOI: 10.4236/alamt.2020.102003                

Abstract

In this paper, we consider a constrained low rank approximation problem: , where E is a given complex matrix, p is a positive integer, and is the set of the Hermitian nonnegative-definite least squares solution to the matrix equation . We discuss the range of p and derive the corresponding explicit solution expression of the constrained low rank approximation problem by matrix decompositions. And an algorithm for the problem is proposed and the numerical example is given to show its feasibility.

Keywords

Low Rank Approximation, Hermitian Matrix, Nonnegative-Definite Matrix, Least Square

1. Introduction

Throughout, let ${ℂ}^{m\times n}$ denote the set of all complex $m\times n$ matrices, $\mathbb{U}\left(n\right)$ the set of all $n\times n$ unitary matrices, and $ℍ\left(n\right)$ the set of all $n\times n$ Hermitian matrices, ${ℍ}_0^{+}\left(n\right)$ the set of Hermitian nonnegative-definite matrices. The symbols I, $A^{\ast }$, $A^{†}$, $r\left(A\right)$ and $\Vert A\Vert$, respectively stand for the identity matrix with the appropriate size, the conjugate transpose, the Moore-Penrose inverse, the rank and the Frobenius norm of $A\in {ℂ}^{m\times n}$. If a square matrix A is inverse, then the inverse matrix of A is denoted by $A^{-1}$.

In the last few years, the structured low rank matrix approximation has been one of the topics of very active research in matrix theory and the applications. We know the empirical data collected in a matrix generally satisfy either the special structure properties or the desirable rank as is expected in the original system. Solving a low rank approximation of a general data matrix is an important task in many disciplines.

The structured low rank approximation problem can be written as follows: given a matrix E, a positive integer p, and a matrix class $\Omega$, find a matrix X satisfying

$\underset{X\in \Omega \mathrm{,}r\left(X\right)\le p}{min}\Vert X-E\Vert \mathrm{,}$

which is concluded by M.T. Chu, et al. in 2003, see [1]. The structured low rank approximation problem and applications associated with different constraint set $\Omega$ have been extensively studied. Generally speaking, $\Omega$ is with linear structure, e.g., symmetric Toeplitz, Hankel, upper Hessenberg, Slyvester, correlation, CP, or banded matrices with fixed bandwidth, etc., which can be referred to [1] - [11]. For examples, in the process of noise removal in signal processing or image enhancement, the underlying covariance matrix with Toeplitz or block Toeplitz structure, see [5] [6]. In the model reduction problem in encoding and filter design, the underlying structure matrix is Hankel, see [7] [12]. In computer algebra, approximating the greatest common divisor of polynomials can be formulated as a low rank approximation problem with Sylvester structure, see [9]. In computing the nearest Euclidean distance, the symmetric nonnegative matrix of rank 5 is a necessary condition for the approximation, see [10]. In the asset portfolio, the structured low rank approximation is about correlation matrix, see [2].

On the other hand, the problems for a (skew) Hermitian solution, Hermitian nonnegative-definite solution, and Hermitian nonnegative-definite least squares solution to the linear matrix equation

$AX{A}^{\ast }=B$ (1.1)

in the literature have been widely studied, where $A\in {ℂ}^{m\times n}$ and $B\in {ℍ}_0^{+}\left(m\right)$ are given matrices. Baksalary [13], Groβ [14], Khatri and Mitra [15], derived a general Hermitian nonnegative-definite solution to (1.1), respectively. Groβ also obtains a representation of the general Hermitian nonnegative-definite solution to Equation (1.1), which admits an easy way to obtain solutions of minimal and maximal rank, respectively. Dai and Lancaster studied a similar problem of Equation (1.1) with the real setting. Zhang and Cheng [16], Wei and Wang [17] studied the fixed rank Hermitian nonnegative definite solution to the matrix equation $AX{A}^{*}=B$ and the least squares problem $AX{A}^{*}=B$ in Frobenius norm, which discussed the ranges of the rank k and derived expressions of the solutions by applying the SVD of the matrix of A. Liu et al., in [18] studied the rank constrained matrix best approximation problem with respect to (skew) Hermitian matrices by the singular value decompostion of B. For the rank constrained of (skew)Hermitian or Hermitian nonnegative definite least squares of (1.1) in spectral norm, the authors applied the norm-preserving dilation theorem and the matrix decomposition to obtain the soulution in [19] [20].

Motivated by the above work, we in this paper study the constrained low rank approximation of Hermitian nonnegative definite matrix. It can be stated as follows.

Problem 1. Given $A\in {ℂ}^{m\times n}$, $B\in {ℂ}^{m\times m}$, $E\in {ℂ}^{n\times n}$, and a positive integer p. Find $\hat{X}$ such that

$\hat{X}\mathrm{<mo>\; :\; </mo>}=arg\underset{X\in \Omega \mathrm{,}r\left(X\right)=p}{min}\Vert X-E\Vert \mathrm{,}$

where $\Omega =\left\{X\mathrm{<mo>\; |\; </mo>}X\in {ℍ}_0^{+}\left(n\right)\mathrm{,}\Vert AX{A}^{\ast }-B\Vert =min\right\}$.

This paper is organized as follows. We give some preliminary results in Section 2. In Section 3, we firstly characterize the matrix set $\Omega$ of the Hermitian nonnegative-definite least squares solution to the matrix equation $AX{A}^{\ast }=B$ by matrix decompositions. Then we use the techniques of partition matrix to discuss the range of p and establish the corresponding explicit solution to Problem 1. In Section 4, an algorithm is designed to determine the solution to Problem 1 and an example is presented to illustrate the results obtained in this paper.

2. Preliminaries

In this section, we give some preliminary results.

Lemma 2.1. (See [21] [22]) For given matrices $M\in {ℂ}^{n_1\times n_1}$, $N\in {ℂ}^{n_2\times n_2}$, and $Y\in {ℂ}^{n_1\times n_2}$, then the partition matrix

$X=\left[\begin{array}{cc}M& Y\\ Y^{\ast }& N\end{array}\right]\in H_0^{+}(\; n\; )$

if and only if

$M\in H_0^{+}\left(n_1\right)\mathrm{,}N-Y^{\ast }{M}^{†}Y\in H_0^{+}\left(n_2\right)\mathrm{,}R\left(Y\right)\subseteq R\left(M\right)\mathrm{<mo>\; ;\; </mo>}$

or

$M\in H_0^{+}\left(n_1\right)\mathrm{,}N=N_0+Y^{\ast }{M}^{†}Y\mathrm{,}Y=M{M}^{†}Y\mathrm{,}$

where $N_0\in H_0^{+}\left(n_2\right)$. Furthermore, the equality

$r\left(X\right)=r\left(M\right)+r\left(N-Y^{\ast }{M}^{†}Y\right)\mathrm{,}$

holds.

The following lemma is cited by Lemma 2.2 in [17].

Lemma 2.2. Given $n\times n$ the Hermitian matrix G which has the form of

$G=Qdiag\left({\Lambda }_{+}\mathrm{,}{\Lambda }_{-}\right)Q^{\ast }\mathrm{,}$

where Q is an $n\times n$ unitary matrix,

${\Lambda }_{+}=diag\left({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_{n_1}\right),{\Lambda }_{-}=diag\left({\lambda }_{n_1+1},{\lambda }_{n_1+2},\cdots ,{\lambda }_n\right),$

and ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_{n_1}>0,{\lambda }_{n_1+1}\le {\lambda }_{n_1+2}\le \cdots \le {\lambda }_n\le 0$. The parameter p is a given nonnegative integer. Then there exists $\tilde{Y}\in H_0^{+}\left(n\right)$ with $r\left(\tilde{Y}\right)=p$ such that

$\tilde{Y}:=\arg \underset{r\left(Y\right)=p,Y\in H_0^{+}\left(n\right)}{min}\Vert Y-G\Vert$

if and only if $0\le p\le n_1$. If $0\le p\le n_1$, then

$\underset{r\left(Y\right)=p,Y\in H_0^{+}\left(n\right)}{\min }\Vert Y-G\Vert ={\displaystyle \underset{k=p+1}{\overset{n}{\sum }}}{\lambda }_i^2.$

Furthermore, if ${\lambda }_p>{\lambda }_{p+1}$, then

$\tilde{Y}=Qdiag\left({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_p,0,\cdots ,0\right)Q^{\ast }.$

If $k<p<l\le n_1$ and ${\lambda }_k>{\lambda }_{k+1}=\cdots ={\lambda }_l>{\lambda }_{l+1}$, then

$\tilde{Y}=Qdiag\left({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_k,{\lambda }_{p}P{P}^{\ast },0,\cdots ,0\right)Q^{\ast },$

where P is an arbitrary matrix satisfying $P\in {ℂ}^{\left(l-k\right)\times \left(p-k\right)}$ and $P^{\ast }P=I_{p-k}$.

3. The General Solution to Problem 1

In this section, we consider the general solution of Problem 1 proposed in Section 1.

Suppose that the matrices $A\in {ℂ}^{m\times n}$, and $B\in {ℂ}^{m\times m}$ are given with $rank\left(A\right)=r_A$. Let $B=B_H+B_S$, where

$B_H=\frac{B+B^{\ast }}{2},B_S=\frac{B-B^{\ast }}{2},$ (3.1)

$B_H$ is an $m\times m$ Hermitian matrix, and $B_S$ is an $m\times m$ skew-Hermitian matrix. Let the singular value decomposition (SVD) of A be as follows

$A=U\left(\begin{array}{cc}{\Sigma }_{r_A}& 0\\ 0& 0\end{array}\right)V^{\ast }\mathrm{,}$ (3.2)

where the diagonal elements of the diagonal matrix ${\Sigma }_{r_A}$ is the singular values of A, and $U\in \mathbb{U}\left(m\right)$, $V\in \mathbb{U}\left(n\right)$. Let

$U^{\ast }{B}_{H}U=\left(\begin{array}{cc}{B}_0& B_1\\ B_1^{\ast }& B_2\end{array}\right),$ (3.3)

where $B_0\in ℍ\left(r_A\right)$, $B_2\in ℍ\left(m-r_A\right)$. By (2)-(4), the unitary invariance of Frobenius norm, and assume

$V^{\ast }XV=\left(\begin{array}{cc}{Y}_0& Y_1\\ Y_1^{\ast }& Y_2\end{array}\right)\mathrm{,}$ (3.4)

$Y_0\in {ℍ}_0^{+}\left(r_A\right)$, $Y_2\in {ℍ}_0^{+}\left(n-r_A\right)$, we get

$\begin{array}{c}{\Vert AX{A}^{\ast }-B\Vert }^2={\Vert AX{A}^{\ast }-B_H\Vert }^2+{\Vert B_S\Vert }^2\\ ={\Vert U\left[\begin{array}{cc}{\Sigma }_{r_A}& 0\\ 0& 0\end{array}\right]V^{\ast }XV\left[\begin{array}{cc}{\Sigma }_{r_A}& 0\\ 0& 0\end{array}\right]U^{\ast }-B_H\Vert }^2+{\Vert B_S\Vert }^2\\ ={\Vert \left[\begin{array}{cc}{\Sigma }_{r_A}& 0\\ 0& 0\end{array}\right]V^{\ast }XV\left[\begin{array}{cc}{\Sigma }_{r_A}& 0\\ 0& 0\end{array}\right]-U^{\ast }{B}_{H}U\Vert }^2+{\Vert B_S\Vert }^2\\ ={\Vert \left[\begin{array}{cc}{\Sigma }_{r_A}& 0\\ 0& 0\end{array}\right]\left[\begin{array}{cc}{Y}_0& Y_1\\ Y_1^{\ast }& Y_2\end{array}\right]\left[\begin{array}{cc}{\Sigma }_{r_A}& 0\\ 0& 0\end{array}\right]-\left[\begin{array}{cc}{B}_0& B_1\\ B_1^{\ast }& B_2\end{array}\right]\Vert }^2+{\Vert B_S\Vert }^2\\ ={\Vert \left[\begin{array}{cc}{\Sigma }_{r_A}{Y}_0{\Sigma }_{r_A}-B_0& -B_1\\ -B_1^{\ast }& -B_2\end{array}\right]\Vert }^2+{\Vert B_S\Vert }^2\\ ={\Vert {\Sigma }_{r_A}{Y}_0{\Sigma }_{r_A}-B_0\Vert }^2+2{\Vert B_1\Vert }^2+{\Vert B_2\Vert }^2+{\Vert B_S\Vert }^2\end{array}$

Then $\underset{X\in \Omega }{min}\Vert AX{A}^{\ast }-B\Vert$ is consistent if and only if

$\underset{Y_0\in H_0^{+}\left(r_A\right)}{\min }\Vert {\Sigma }_{r_A}{Y}_0{\Sigma }_{r_A}-B_0\Vert .$ (3.5)

is solvable.

We obtain the following result.

Theorem 3.1. Given $A\in {ℂ}^{m\times n}$ and $B\in {ℂ}^{m\times m}$ with $rank\left(A\right)=r_A$. The notation $B_H$ is defined in (2). Let the SVD of A be as (3). Partition $U^{\ast }{B}_{H}U$ as (4) with $B_0\in ℍ\left(r_A\right)$, $B_2\in ℍ\left(m-r_A\right)$. Suppose the matrix $B_0$ has s positive eigenvalues, then $B_0$ has the following decomposition

$B_0=Wdiag\left({\Lambda }_{+}\mathrm{,}{\Lambda }_{-}\right)W^{\ast }\mathrm{,}$ (3.6)

where $W\in \mathbb{U}\left(r_A\right)$, ${\Lambda }_{+}=diag\left({\lambda }_1\mathrm{,}\cdots \mathrm{,}{\lambda }_s\right)$, ${\lambda }_1\ge \cdots \ge {\lambda }_s>0$, ${\Lambda }_{-}=diag\left({\lambda }_{s+1},\cdots ,{\lambda }_{r_A}\right)$, ${\lambda }_{s+1}\le \cdots \le {\lambda }_{r_A}\le 0$. And the eigendecomposition of ${\Sigma }_{r_A}^{-1}Wdiag\left({\Lambda }_{+},0\right)W^{\ast }{\Sigma }_{r_A}^{-1}$ is

${\Sigma }_{r_A}^{-1}Wdiag\left({\Lambda }_{+},0\right)W^{\ast }{\Sigma }_{r_A}^{-1}=L\left[\begin{array}{cc}{D}_1& 0\\ 0& 0\end{array}\right]L^{\ast },$ (3.7)

in which $L\in \mathbb{U}\left(r_A\right)$ and a diagonal matrix $D_1\in {ℍ}^{+}\left(s\right)$. Assume

$Q=V\left[\begin{array}{cc}L& 0\\ 0& I_{n-r_A}\end{array}\right]\mathrm{.}$ (3.8)

Then the Hermitian nonnegative definite solution to the least squares solution of $AX{A}^{\ast }=B$ can be expressed as

$X=Q\left[\begin{array}{ccc}{D}_1& 0& Y_{11}\\ 0& 0& 0\\ Y_{11}^{\ast }& 0& Y_2\end{array}\right]Q^{\ast }$ (3.9)

where $Y_{11}\in {ℂ}^{s\times \left(n-r_A\right)}$ and $Y_2-Y_{11}^{\ast }{D}_1^{-1}{Y}_{11}\in {ℍ}_0^{+}\left(n-r\left(A\right)\right)$.

Proof. According to above analysis, the matrix equation $AX{A}^{\ast }=B$ has the Hermitian nonnegative-definite least squares solution if and only if (3.5) is consistent. By Lemma 2.2 and (3.6), the Formula (3.5) holds if and only if

$Y_0={\Sigma }_{r_A}^{-1}Wdiag\left({\Lambda }_{+},0\right)W^{\ast }{\Sigma }_{r_A}^{-1}.$ (3.10)

It follows from $r\left(Y_0\right)=s$ and $Y_0\in {ℍ}_0^{+}\left(r\left(A\right)\right)$ that the eigendecomposition of $Y_0$ in (3.10) has the form of (3.7). Substituting (3.10) into (3.4), we get

$X=V\left[\begin{array}{cc}L\left[\begin{array}{cc}{D}_1& 0\\ 0& 0\end{array}\right]L^{\ast }& Y_1\\ Y_1^{\ast }& Y_2\end{array}\right]V^{\ast }\mathrm{.}$ (3.11)

Assume $L^{\ast }{Y}_1=\left[\begin{array}{c}{Y}_{11}\\ Y_{12}\end{array}\right]$, $Y_{11}\in {ℂ}^{s\times \left(n-r_A\right)}$, $Y_{12}\in {ℂ}^{\left(r_A-s\right)\times \left(n-r_A\right)}$, then by (3.8), $Q\in \mathbb{U}\left(n\right)$ and (3.11) becomes

$\begin{array}{c}X=V\left[\begin{array}{cc}L\left(\begin{array}{cc}{D}_1& 0\\ 0& 0\end{array}\right)L^{\ast }& L\left(\begin{array}{c}{Y}_{11}\\ Y_{12}\end{array}\right)\\ \left(\begin{array}{cc}{Y}_{11}^{\ast }& Y_{12}^{\ast }\end{array}\right)L^{\ast }& Y_2\end{array}\right]V^{\ast }\\ =V\left[\begin{array}{cc}L& 0\\ 0& I_{n-r_A}\end{array}\right]\left[\begin{array}{ccc}{D}_1& 0& Y_{11}\\ 0& 0& Y_{12}\\ Y_{11}^{\ast }& Y_{12}^{\ast }& Y_2\end{array}\right]\left[\begin{array}{cc}{L}^{\ast }& 0\\ 0& I_{n-r_A}\end{array}\right]V^{\ast }\\ =Q\left[\begin{array}{ccc}{D}_1& 0& Y_{11}\\ 0& 0& Y_{12}\\ Y_{11}^{\ast }& Y_{12}^{\ast }& Y_2\end{array}\right]Q^{\ast }\end{array}$ (3.12)

It implies that $X\in {ℍ}_0^{+}\left(n\right)$ in (3.12) if and only if $\left[\begin{array}{ccc}{D}_1& 0& Y_{11}\\ 0& 0& Y_{12}\\ Y_{11}^{\ast }& Y_{12}^{\ast }& Y_2\end{array}\right]\in {ℍ}_0^{+}\left(n\right)$. By Lemma 2.1, it is equivalent to $\left[\begin{array}{ccc}{D}_1& 0& Y_{11}\\ 0& 0& 0\\ Y_{11}^{\ast }& 0& Y_2\end{array}\right]$, where $Y_2-Y_{11}^{\ast }{D}_1^{-1}{Y}_{11}\in {ℍ}_0^{+}\left(n-r\left(A\right)\right)$.

By Theorem 3.1, for $X\in \Omega$ defined in Problem 1, X has the form of (3.9) with $Y_{11}\in {ℂ}^{s\times \left(n-r_A\right)}$ and $Y_2-Y_{11}^{\ast }{D}_1^{-1}{Y}_{11}\in {ℍ}_0^{+}\left(n-r\left(A\right)\right)$. Now we consider Problem 1, and give their explicit expression of the solution.

Theorem 3.2. Given $E\in {ℂ}^{n\times n}$ and $\Omega$ in problem 1 is nonempty. The notations are the same as Theorem 3.1, and the solution set of $\Omega$ is (10). Let

$E_1=\frac{E+E^{*}}{2},E_2=\frac{E-E^{*}}{2}.$ (3.13)

The eigenvalue decomposition of $Q^{\ast }{E}_{1}Q$ has the form of

$Q^{\ast }{E}_{1}Q=T\left[\begin{array}{cc}{\Psi }_{+}& 0\\ 0& {\Psi }_{-}\end{array}\right]T^{*},$ (3.14)

where $T\in \mathbb{U}\left(n\right)$, ${\Psi }_{+}=diag\left({\psi }_1\mathrm{,}\cdots \mathrm{,}{\psi }_d\right)$, ${\psi }_1\ge \cdots \ge {\psi }_d>0$, ${\Psi }_{-}=diag\left({\psi }_{d+1}\mathrm{,}\cdots \mathrm{,}{\psi }_n\right)$, ${\psi }_{d+1}\le \cdots \le {\psi }_n\le 0$. Suppose

$T\left[\begin{array}{cc}{\Psi }_{+}& 0\\ 0& 0\end{array}\right]T^{*}=\left[\begin{array}{ccc}{E}_{11}& E_{12}& E_{13}\\ E_{12}^{\ast }& E_{22}& E_{23}\\ E_{13}^{\ast }& E_{23}^{\ast }& E_{33}\end{array}\right],$ (3.15)

where $E_{11}\in ℍ\left(s\right)$, $E_{13}\in {ℂ}^{s\times \left(n-r_A\right)}$, and $E_{33}\in ℍ\left(n-r_A\right)$. And the eigenvalue decomposition of $E_{33}-E_{13}^{\ast }{D}_1^{-1}{E}_{13}$ is as follows

$E_{33}-E_{13}^{\ast }{D}_1^{-1}{E}_{13}=H\left[\begin{array}{cc}{\Delta }_{+}& \\ & {\Delta }_{-}\end{array}\right]H^{\ast },$ (3.16)

where $H\in \mathbb{U}\left(n-r_A\right)$, ${\Delta }_{+}=diag\left(u_1\mathrm{,}\cdots \mathrm{,}{u}_t\right)$, $u_1\ge \cdots \ge u_t>0$, ${\Delta }_{-}=diag\left(u_{t+1},\cdots ,u_{n-r_A}\right)$, $u_{t+1}\le \cdots \le u_{n-r_A}\le 0$. For a positive integer p, $\underset{r\left(X\right)=p\mathrm{,}X\in \Omega }{min}\Vert X-E\Vert$ is consistent if and only if

$s\le p\le s+n-r_A\mathrm{.}$ (3.17)

Then the solution $\hat{X}$ in Problem 1 is given as follows from the three cases:

1) If $p=s$, then

$\hat{X}=Q\left[\begin{array}{cc}{D}_1& 0\\ 0& 0\end{array}\right]Q^{\ast }.$ (3.18)

2) If $s<p\le s+t$, then

$\hat{X}=Q\left[\begin{array}{ccc}{D}_1& 0& E_{13}\\ 0& 0& 0\\ E_{13}^{\ast }& 0& Y_2\end{array}\right]Q^{\ast },$ (3.19)

where

$Y_2=Hdiag\left(u_1,\cdots ,u_{p-s},0,\cdots ,0\right)H^{\ast }+E_{13}^{*}{D}_1^{-1}{E}_{13};$ (3.20)

3) If $p>s+t$, then X is the form of (3.19), where

$Y_2=Hdiag\left(u_1,\cdots ,u_{t}P{P}^{\ast },0,\cdots ,0\right)H^{\ast }+E_{13}^{*}{D}_1^{-1}{E}_{13},$ (3.21)

and P is an arbitary matrix satisfying $P^{\ast }P=I_{p-s-t}$.

Proof. According to Theorem 3.1, if $X\in \Omega$, then X has the formula of (3.9), where $Q\in \mathbb{U}\left(n\right)$, $D_1\in {ℍ}^{+}\left(s\right)$ is a diagonal matrix, $Y_{11}\in {ℂ}^{s\times \left(n-r_A\right)}$ and $Y_2-Y_{11}^{\ast }{D}_1^{-1}{Y}_{11}\in {ℍ}_0^{+}\left(n-r_A\right)$. By Lemma 2.1, $r\left(X\right)=r\left(D_1\right)+r\left(Y_2-Y_{11}^{\ast }{D}_1^{-1}{Y}_{11}\right)$. Therefore $s\le r\left(X\right)=p\le s+n-r_A$.

1) If $p=s$, then $Y_2=0$ and $Y_{11}=0$ in (3.9). We get (3.18).

2) If $s<p\le s+n-r_A$. Furthermore, we know $E=E_1\oplus E_2$, where $E_1\mathrm{,}{E}_2$ are defined as (3.13). By the unitary invariance of Frobenius norm that

$\begin{array}{c}{\Vert X-E\Vert }^2={\Vert X-E_1\Vert }^2+{\Vert E_2\Vert }^2\\ ={\Vert Q\left[\begin{array}{ccc}{D}_1& 0& Y_{11}\\ 0& 0& 0\\ Y_{11}^{\ast }& 0& Y_2\end{array}\right]Q^{\ast }-E_1\Vert }^2+{\Vert E_2\Vert }^2\\ ={\Vert \left[\begin{array}{ccc}{D}_1& 0& Y_{11}\\ 0& 0& 0\\ Y_{11}^{\ast }& 0& Y_2\end{array}\right]-Q^{\ast }{E}_{1}Q\Vert }^2+{\Vert E_2\Vert }^2\\ ={\Vert \left[\begin{array}{ccc}{D}_1& 0& Y_{11}\\ 0& 0& 0\\ Y_{11}^{\ast }& 0& Y_2\end{array}\right]-T\left[\begin{array}{cc}{\Psi }_{+}& 0\\ 0& 0\end{array}\right]T^{*}\Vert }^2+{\Vert T\left[\begin{array}{cc}0& 0\\ 0& {\Psi }_{-}\end{array}\right]T^{*}\Vert }^2+{\Vert E_2\Vert }^2\end{array}$

$\begin{array}{l}={\Vert \left[\begin{array}{ccc}{D}_1-E_{11}& -E_{12}& Y_{11}-E_{13}\\ -E_{12}^{\ast }& -E_{22}& -E_{23}\\ Y_{11}^{\ast }-E_{13}^{\ast }& -E_{23}^{\ast }& Y_2-E_{33}\end{array}\right]\Vert }^2+{\Vert {\Psi }_{-}\Vert }^2+{\Vert E_2\Vert }^2\\ ={\Vert D_1-E_{11}\Vert }^2+2{\Vert E_{12}\Vert }^2+2{\Vert Y_{11}-E_{13}\Vert }^2+{\Vert E_{22}\Vert }^2+2{\Vert E_{23}\Vert }^2\\ +{\Vert Y_2-E_{33}\Vert }^2+{\Vert {\Psi }_{-}\Vert }^2+{\Vert E_2\Vert }^2\end{array}$

Hence, $\underset{r\left(X\right)=p\mathrm{,}X\in \Omega }{min}\Vert X-E\Vert$ is consistent if and only if

$\underset{Y_{11}\in {ℂ}^{s\times \left(n-r_A\right)}}{min}\Vert Y_{11}-E_{13}\Vert$ (3.22)

and

$\underset{Y_2-Y_{11}^{\ast }{D}_1^{-1}{Y}_{11}\in {ℍ}_0^{+}\left(n-r_A\right),r\left(Y_2-Y_{11}^{\ast }{D}_1^{-1}{Y}_{11}\right)=p-s}{min}\Vert Y_2-E_{33}\Vert$ (3.23)

are solvable. (3.22) is consistent if and only if $Y_{11}=E_{13}$. And (3.23) holds if and only if there exists $Z\in {ℍ}_0^{+}\left(n-r_A\right)$ such that $\underset{r\left(Z\right)=p-s}{\min }\Vert Z-\left(E_{33}-E_{13}^{\ast }{D}_1^{-1}{E}_{13}\right)\Vert$

holds. Make the eigendecomposition of $\left(E_{33}-E_{13}^{\ast }{D}_1^{-1}{E}_{13}\right)$ as (3.16). By Lemma 2.2, we discuss the problem from two cases:

1) When $p-s\le t$, we take $Y_2$ is of (3.20). The explicit expression of the solution to Problem 1 is (3.19) with (3.20).

2) When $p-s>t$, we take $Y_2$ is of (3.21). In this case, we obtain the representation of the solution to Problem 1, which has the form of (3.19) with (3.21).

The proof is completed.

4. Numerical Examples

We in this section propose an algorithm for finding the solution of Problem 1 and give illustrative numerical example.

Algorithm 4.1. 1) Input $A\mathrm{,}B\mathrm{,}E$ ;

2) Calculate $r_A\mathrm{,}{B}_H$ by (3.1), $E_1$ by (3.13);

3) Make the SVD of A with the form of (3.2);

4) Calculate $B_0$ by (3.3), make the eigendecomposition of $B_0$ with the form of (3.6), and compute $s\mathrm{<mo>\; ;\; </mo>}$

5) If p does not satisfy (3.17), then the solution set of Problem 1 is empty and terminate the algorithm. Otherwise, continue with the following step;

6) Make the eigendecomposition of ${\Sigma }_{r_A}^{-1}Wdiag\left({\Lambda }_{+}\mathrm{,0}\right)W^{\ast }{\Sigma }_{r_A}^{-1}$ with the form of (3.7);

7) Calculate $Q\mathrm{,}{E}_1$, by (3.8), (3.13), respectively;

8) Make the eigenvalue decomposition of $Q^{\ast }{E}_{1}Q$ by 3.14. and Compute $E_{13}\mathrm{,}{E}_{33}$ by (3.15);

9) If $p=s$, calculate X by (3.18), or go to step 10;

10) If $p>s$, make the eigendecomposition of $E_{33}-E_{13}^{\ast }{D}_1^{-1}{E}_{13}$ with the form of (3.16) and calculate t;

11) If $0<p-s\le t$, calculate X by (3.19) with (3.20); otherwise, go to (12);

12) If $p-s>t$, calculate X by (3.19) with (3.21).

Example 4.2. Suppose $n=6$, $A\in {ℂ}^{5\times 6}$, $B\in {ℂ}^{6\times 6}$, $E\in {ℂ}^{6\times 6}$ and

$A=\left[\begin{array}{cccccc}-2.2100+1.2000i& 2.0000-1.0000i& 0.0000+0.0000i& -0.0900+1.3500i& 4.3200-2.3100i& 1.2120+1.9804i\\ 0.0000+3.2510i& 0.0000+0.0000i& 2.1800-0.3200i& -0.2300+1.5000i& -0.1724-0.0995i& \\ 1.0500-2.0000i& 2.4000+1.2500i& 0.0000+0.0000i& 0.0000+3.2106i& -1.6080+0.0000i& 2.2560+0.0000i\\ 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i\\ 3.2000+0.0000i& -4.2000+1.2000i& 0.0000+0.0000i& 1.1025-0.2400i& -0.8600-0.2408i& 1.2010+0.7000i\end{array}\right],$

$B=\left[\begin{array}{ccccc}4.2000+2.6500i& 1.5800-0.2300i& 2.2020+1.5680i& 0.0000+2.4200i& 2.5160-0.7600i\\ 1.0120-0.2820i& -3.5100+1.5600i& 1.3800-0.8000i& 1.3050+2.8000i& 1.8800-0.7890i\\ 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i\\ 2.9000-1.0680i& 0.0000-1.5300i& 5.6800+1.6030i& -4.0150+2.1200i& 3.4200-2.6500i\\ 2.9500+0.0000i& 2.4400-0.6405i& 1.4800-1.0503i& 3.2750-1.4980i& 0.0000+1.3450i\end{array}\right],$

$E=\left[\begin{array}{cccccc}0.1020+0.0000i& -1.2400+0.0056i& 0.1460-0.2320i& 0.5000+0.0000i& -0.1520+0.1270i& 1.2000+0.0045i\\ -1.2400-0.0056i& -0.0040+0.0000i& -0.1630-0.0550i& -0.2390-0.0920i& 0.1400-0.1800i& 0.0000+0.0000i\\ 0.1460+0.2320i& -0.1630+0.0550i& 1.0000+0.0000i& 0.2310+0.0000i& -0.1650-0.0550i& 0.0000+0.2040i\\ 0.5000+0.0000i& -0.2390+0.0920i& 0.2310+0.0000i& 0.0800+0.0000i& -0.2400-0.0920i& 0.0000+0.0000i\\ -0.1520-0.1270i& 0.1400+0.1800i& -0.1650+0.0550i& -0.2400+0.0920i& -0.1024+0.0000i& -0.0002+0.0250i\\ 1.2000-0.0045i& 0.0000+0.0000i& 0.0000-0.2040i& 0.0000+0.0000i& -0.0002-0.0250i& 0.0256+0.0000i\end{array}\right].$

We get $rank\left(A\right)=4$ and $s=2$. According to Theorem 3.2, Problem 1 is solvable if and only if $2\le p\le 4$. By Algorithm 4.1, we show the corresponding explicit expression of the solution to Problem 1 for $p=2,3,4$, respectively. When $p=2$, the solution expression in Problem 1 is as follows

$\hat{X}=\left[\begin{array}{cccccc}1.2974-0.0000i& -0.2777-0.1086i& 0.0000+0.0000i& 0.3705+1.1896i& 2.0296+0.4850i& 0.5477+0.1255i\\ -0.2777+0.1086i& 0.1536-0.0000i& -0.0000-0.0000i& -0.2185-0.1705i& -0.6026-0.1101i& -0.0764+0.0194i\\ 0.0000-0.0000i& -0.0000+0.0000i& 0.0000-0.0000i& 0.0000+0.0000i& 0.0000-0.0000i& 0.0000-0.0000i\\ 0.3705-1.1896i& -0.2185+0.1705i& 0.0000-0.0000i& 1.2482-0.0000i& 0.9739-1.5609i& 0.2479-0.4986i\\ 2.0296-0.4850i& -0.6026+0.1101i& 0.0000+0.0000i& 0.9739+1.5609i& 3.9124+0.0000i& 0.8259+0.0973i\\ 0.5477-0.1255i& -0.0764-0.0194i& 0.0000+0.0000i& 0.2479+0.4986i& 0.8259-0.0973i& 0.2744-0.0000i\end{array}\right],$

and $\underset{X\in \Omega ,r\left(X\right)=2}{\min }\Vert X-E\Vert =6.8009$. When $p=3$, we obtain the solution of Problem 1 is

$\hat{X}=\left[\begin{array}{cccccc}1.3943-0.0000i& -0.2179-0.1781i& 0.1028-0.0987i& 0.3658+1.1650i& 2.0332+0.5482i& 0.5969+0.1872i\\ -0.2179+0.1781i& 0.2064-0.0000i& 0.1206-0.0503i& -0.1991-0.1300i& -0.6215-0.0512i& -0.0834+0.0625i\\ 0.1028+0.0987i& 0.1206+0.0503i& 0.9996-0.0000i& 0.1914+0.0274i& -0.0726+0.0312i& -0.0765+0.0560i\\ 0.3658-1.1650i& -0.1991+0.1300i& 0.1914-0.0274i& 1.1509-0.0000i& 0.9242-1.5232i& 0.2816-0.4730i\\ 2.0332-0.5482i& -0.6215+0.0512i& -0.0726-0.0312i& 0.9242+1.5232i& 3.9276+0.0000i& 0.8785+0.0925i\\ 0.5969-0.1872i& -0.0834-0.0625i& -0.0765-0.0560i& 0.2816+0.4730i& 0.8785-0.0925i& 0.3103-0.0000i\end{array}\right].$

and $\underset{X\in \Omega ,r\left(X\right)=3}{\min }\Vert X-E\Vert =6.7283$. When $p=4$, the solution can be expressed as $\hat{X}=X_1+X_2$, where

$X_1=\left[\begin{array}{cccccc}1.3774+0.0000i& -0.2359-0.1724i& 0.0365+0.0116i& 0.3563+1.1835i& 2.0347+0.5457i& 0.5957+0.1710i\\ -0.2359+0.1724i& 0.1853-0.0000i& 0.0132+0.0454i& -0.2154-0.1134i& -0.6191-0.0534i& -0.0793+0.0448i\\ 0.0365-0.0116i& 0.0132-0.0454i& 0.0195+0.0000i& 0.0339+0.0381i& -0.0503+0.0311i& 0.0245-0.0159i\\ 0.3563-1.1835i& -0.2154+0.1134i& 0.0339-0.0381i& 1.1254-0.0000i& 0.9277-1.5230i& 0.2986-0.4835i\\ 2.0347-0.5457i& -0.6191+0.0534i& -0.0503-0.0311i& 0.9277+1.5230i& 3.9271+0.0000i& 0.8762+0.0942i\\ 0.5957-0.1710i& -0.0793-0.0448i& 0.0245+0.0159i& 0.2986+0.4835i& 0.8762-0.0942i& 0.2946-0.0000i\end{array}\right]$

and $X_2=G\left[\begin{array}{cc}0& 0\\ 0& 1.0597P{P}^{\mathrm{<mo>\; *\; </mo>}}\end{array}\right]G^{\mathrm{<mo>\; *\; </mo>}}$ with

$G=\left[\begin{array}{cccccc}0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.1015+0.0752i& -0.1452-0.4186i\\ 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0833+0.1140i& -0.0157-0.4949i\\ 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& -0.0930+0.9572i& -0.1758+0.2104i\\ 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& -0.0253+0.1528i& 0.3757-0.3926i\\ 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0022-0.0217i& -0.0494+0.0586i\\ 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0000+0.0000i& 0.0798-0.0919i& -0.4129+0.1083i\end{array}\right]$

and $P\in {ℂ}^{2\times 2}$ satisfying $P^{*}P=I_2$.

Remark The Algorithm 4.1 can be applied for small sizes of matrices in Problem 1. In the process of computation, it only involves once singular value decomposition and four times eigendecompositions. Hence it has good numerical stability.

5. Conclusion

In this paper, we have studied the constrained low rank approximation problem $\underset{r\left(X\right)=p\mathrm{,}X\in \Omega }{min}\Vert X-E\Vert$, where $\Omega$ is the set of the Hermitian nonnegative-definite least squares solution to the matrix equation $AX{A}^{\ast }=B$, by the matrix decompositions and partitioned matrix techniques. We have established the necessary and sufficient condition for solvability of the problem. We have also derived the corresponding explicit solution expressions for constraints of different rank range. And the algorithm has been presented and the numerical example shows its feasibility.

Fund

This research was supported by the Natural Science Foundation of China (11601328), and the research fund of Shanghai Lixin University of Accounting and Finance (AW-22-2201-00118).

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Chu, M.T., Funderlic, R.E. and Plemmons, R.J. (2003) Structured Low Rank Approximation. Linear Algebra and its Applications, 366, 157-172. https://doi.org/10.1016/S0024-3795(02)00505-0
[2]	Duan, X.F., Bai, J.C., Zhang, M.J. and Zhang, X.J. (2014) On the Generalized Low Rank Approximation of the Correlation Matrices Arising in the Asset Portfolio. Linear Algebra and its Applications, 461, 1-17. https://doi.org/10.1016/j.laa.2014.07.026
[3]	Markovsky, I. (2008) Structured Low-Rank Approximation and Its Applications. Automatica, 44, 891-909. https://doi.org/10.1016/j.automatica.2007.09.011
[4]	Zhang, Z.Y. and Wu, L.X. (2003) Optimal Low-Rank Approximation to a Correlation Matrix. Linear Algebra and its Applications, 364, 161-187. https://doi.org/10.1016/S0024-3795(02)00551-7
[5]	Li, H.B., Stoica, E.P. and Li, J. (1999) Computationally Efficient Maximum Likelihood Estimation of Structured Covariance Matrices. IEEE Transactions on Signal Processing, 47, 1314-1323. https://doi.org/10.1109/78.757219
[6]	Williams, D.E. and Johnson, D.H. (1993) Robust Estimation on Structured Covariance Matrices. IEEE Transactions on Signal Processing, 41, 2891-2906. https://doi.org/10.1109/78.236511
[7]	De Moor, B. (1994) Total Least Squares for Affinely Structured Matrices and the Noisy Realization Problem. IEEE Transactions on Signal Processing, 42, 3104-3113. https://doi.org/10.1109/78.330370
[8]	Park, H., Lei, Z. and Rosen, J.B. (1999) Low Rank Approximation of a Hankel Matrix by Structured Total Least Norm. BIT Numerical Mathematics, 39, 757-779. https://doi.org/10.1023/A:1022347425533
[9]	Karmarkar, N.K. and Lakshman, Y.N. (1998) On Approximate GCDs of Unvariate Polynomials. Journal of Symbolic Computation, 26, 653-666. https://doi.org/10.1006/jsco.1998.0232
[10]	Glunt, W., Hayden, T.L., Hong, S. and Wells, J. (1990) An Alternating Projection Algorithm for Computing the Nearest Euclidean Distance Matrix. SIAM Journal on Matrix Analysis and Applications, 11, 589-600. https://doi.org/10.1137/0611042
[11]	Fan, J.Y. and Zhou, A.W. (2016) The CP-Matrix Approximation Problem. SIAM Journal on Matrix Analysis and Applications, 37, 171-194. https://doi.org/10.1137/15M1012086
[12]	Huckle, T., Serra-Capizzano S. and Tablino-Possio, C. (2004) Preconditioning Strategies for Hermitian Indefinite Toeplitz Linear Systems SIAM Journal on Scientific Computing, 25, 1633-1654. https://doi.org/10.1137/S1064827502416332
[13]	Baksalary, J.K. (1984) Nonnegative Definite and Positive Definite Solutions to the Matrix Equation AXAH=B. Linear and Multilinear Algebra, 16, 133-139. https://doi.org/10.1080/03081088408817616
[14]	Groβ, J. (2000) Nonnegative-Define and Positive Solutions to the Matrix Equation AXAH=B—Revisited. Linear Algebra and its Applications, 321, 123-129. https://doi.org/10.1016/S0024-3795(00)00033-1
[15]	Khatri, C.G. and Mitra, S.K. (1976) Hermitian and Nonnegative Definite Solutions of Linear Matrix Equations. SIAM Journal on Applied Mathematics, 31, 579-585. https://doi.org/10.1137/0131050
[16]	Zhang, X. and Cheng, M. (2003) The Rank-Constrained Hermitian Nonnegative-Definite and Positive-Definite Solutions to the Matrix Equation AXAH=B. Linear Algebra and its Applications, 370, 163-174. https://doi.org/10.1016/S0024-3795(03)00385-9
[17]	Wei, M.S. and Wang, Q. (2007) On Rank-Constrained Hermitian Nonnegative-Definite Least Squares Solutions to the Matrix Equation AXAH=B. International Journal of Computer Mathematics, 84, 945-952. https://doi.org/10.1080/00207160701458344
[18]	Liu, X.F., Li, W. and Wang, H.X. (2017) Rank Constrained Matrix Best Approximation Problem with Respect to (Skew) Hermitian Matrices. Journal of Computational and Applied Mathematics, 319, 77-86. https://doi.org/10.1016/j.cam.2016.12.029
[19]	Wei, M. and Shen, D. (2012) Minimum Rank Solutions to the Matrix Approximation Problems in the Spectral Norm. SIAM Journal on Matrix Analysis and Applications, 33, 940-957. https://doi.org/10.1137/110851134
[20]	Shen, D., Wei, M. and Liu, Y. (2015) Minimum Rank (Skew) Hermitian Solutions to the Matrix Approximation Problem in the Spectral Norm. Journal of Computational and Applied Mathematics, 288, 351-365. https://doi.org/10.1016/j.cam.2015.04.033
[21]	Zhang, F.Z. (1999) Matrix Theory: Basic Results and Techniques. Springer, New York.
[22]	Albert, A. (1969) Condition for Positive and Nonnegative Definite in Terms of Pseudoinverse. SIAM Journal on Applied Mathematics, 17, 434-440. https://doi.org/10.1137/0117041