Condition numbers of the minimum norm least squares solution for the least squares problem involving Kronecker products

1.   Introduction

Consider the least squares (LS) problem involving Kronecker products

where $A\in \mathbb{R}^{m\times n}$, $B\in \mathbb{R}^{p\times q}$, $b\in \mathbb{R}^{mp}$, and where the Kronecker product ^[13] is defined by

The LS problems involving Kronecker products of the type (1.1) arise in many areas of application including signal and image processing, photogrammetry, fast transform algorithms, the Lyapunov approach to stability theory, circuits and systems, and stochastic matrices ^[8,19]. Therefore, the LS problems involving Kronecker products have attracted many researchers to study its algorithms ^[2,9,10,18].

For a given problem, a condition number measures the worst-case sensitivity of its solution to small perturbations in the input data, whereas backward errors reveal the stability of a numerical method. Combined with the backward error, a condition number can provide a first-order upper bound on the error in the computational solution ^[15]. In ^[22], the authors gave the upper bounds on the normwise, mixed and componentwise condition numbers for the Kronecker product linear systems $(A\otimes B)x = b$. The level-2 condition numbers for the Kronecker product linear systems have studied by Kang and Xiang ^[17]. Xiang and Wei ^[23] derived the explicit expressions of the normwise, mixed and componentwise condition numbers for the Kronecker product linear systems with multiple right-hand sides. For the LS problem involving Kronecker products of (1.1), Diao et al. ^[7] have studied its conditioning theory when $A$ and $B$ are of full column rank. Chen and Li ^[5] presented explicit expressions for normwise, mixed and componentwise condition numbers for the weighted least squares problem involving Kronecker when $A$ and $B$ are of full column rank. In this paper, we will present the upper bounds for the normwise, mixed and componentwise condition numbers of the LS problem (1.1) when $A$ or $B$ is of rank deficient.

According to the fact that $\text{rank}(A\otimes B) = \text{rank}(A)\text{rank}(B)$, it follows that $A\otimes B$ is rank deficient when $A$ or $B$ is of rank deficient. In this case, the LS solution to (1.1) always exists but it is nonunique. Therefore the unique minimum norm LS solution $x_{_{LS}} = (A\otimes B)^† b = (A^†\otimes B^†)b$ is considered, where $A^†$ denotes the Moore-Penrose inverse of $A$. Moreover, when $A\otimes B$ is a rank deficient matrix, small changes to $A$ or $B$ can produce large changes to $x_{_{LS}} = (A^†\otimes B^†)b$, see Example 1. In other words, a condition number of $x_{_{LS}}$ with respect to rank deficient $A\otimes B$ does not exist or is "infinite". Hence, in this section, we present the normwise, mixed and componentwise condition numbers of the LS problem (1.1) by restricting changes to the perturbation matrices $\Delta A$ or $\Delta B$, i.e. $\Delta A\in\mathcal{S}$ or $\Delta B\in\mathcal{T}$, where

and

Here $R(A)$ denotes the range of $A$.

Example 1. Let

By simple computations, we have

and

Throughout the paper, for given positive integers $m$ and $n$, denote by $\mathbb{R}^{n}$ the space of $n$-dimensional real column vectors, by $\mathbb{R}^{m\times n}$ the space of all $m\times n$ real matrices, and by $\|\cdot\|_2$ and $\|\cdot\|_F$ the $2$-norm and Frobenius norm of their arguments, respectively. Given a matrix $X = [x_{ij}]\in\mathbb{R}^{m\times n}$, $\|X\|_{\max}$, $X^†$, $X^T$ denote the max norm, given by $\|X\|_{\max} = \max\limits_{i, j}|x_{ij}|$, the Moore-Penrose inverse and the transpose of $X$, respectively, and $|X|$ is the matrix whose elements are $|x_{ij}|$. For the matrices $X = [x_{ij}]$, $Y = [y_{ij}]\in\mathbb{R}^{m\times n}$, $X\leq Y$ means $x_{ij}\leq y_{ij}$ for all $i, j$ and we define $\frac{X}{Y} = [z_{ij}]\in \mathbb{R}^{m\times n}$ by

The following lemmas will be used in the later discussion.

Lemma 1.1. ^[13] For any matrix $X = (x_{ij})\in R^{m\times n}$, $Y\in R^{p\times q}$ and $Z\in R^{n\times p}$, we have

Furthermore, with $\mathit{\text{vec}}(\cdot)$ stacking columns, we have

where $a\in \mathbb{R}^{m}$, $c\in \mathbb{R}^{n}$, $K_{mn}\in \mathbb{R}^{mn\times mn}$ is the permutation matrix defined by

Here each $E_{ij}\in \mathbb{R}^{m\times n}$ has entry $1$ in position $(i, j)$ and all other entries are zero.

Lemma 1.2. ^[12] If $E\in \mathbb{R}^{n\times n}$ and $\|E\|_2 < 1$, then $I_n-E$ is nonsingular and

Lemma 1.3. ^[3] If $A$, $\Delta A\in \mathbb{R}^{m\times n}$ satisfy $\|A^†\Delta A\|_2 < 1$, $R(\Delta A)\subseteq R(A)$ and $R((\Delta A)^T)\subseteq R(A^T)$, then

2.   Normwise condition numbers

The following weighted Frobenius norm

was first used by Gratton for deriving the normwise condition number for the linear least squares problem ^[14]. Here $\|\diamond\|_F$ denotes the Frobenius norm of a matrix, and $\|\diamond\|_2$ denotes the spectral norm of a matrix or the Euclidean norm of a vector. We will call the latter $2$-norm uniformly later in this paper. Subsequently, this kind of norm was used for the partial condition number for the linear least squares problem ^[1] and the normwise condition number of the truncated singular value solution of a linear ill-posed problem ^[4]. A more general weighted Frobenius norm $\left\|\left[\begin{matrix}AT & \beta b\end{matrix}\right]\right\|_F$, where $T$ is a positive diagonal matrix, is sometimes chosen. This is the case, for instance, in ^[6], which gives the explicit expressions for the normwise, mixed and componentwise condition numbers of the Tikhonov regularization using this norm. In this paper, we use the weighted Frobenius norm and weighted $2$-norm which defined by

and

with $\alpha, \; \beta, \; \gamma > 0$. These norms are very flexible since they allow us to monitor the perturbations on $A$, $B$ and $b$. For instance, large values of $\alpha$ enable us to obtain condition number problems where mainly $B$ and $b$ are perturbed.

Consider the perturbed LS problem of (1.1)

where $\Delta A$, $\Delta B$ and $\Delta b$ are the perturbations of the input data $A$, $B$ and $b$, respectively. The unique minimum norm LS solution to (2.1) is $\widetilde{x}_{_{LS}} = \left((A+\Delta A)^† \otimes (B+\Delta B)^†\right)(b+\Delta b)$. We let the change in the solution be $\Delta x = \widetilde{x}_{_{LS}}-x_{_{LS}}$.

Theorem 2.1. When $A$ and $B$ are of rank deficient, the condition number

satisfies

where $P = (x_{_{LS}}^T\otimes A^†\otimes B^†)(I_n\otimes K_{qm}\otimes I_p)(I_{mn}\otimes\mathit{\text{vec}}(B))$ and $Q = (x_{_{LS}}^T\otimes A^†\otimes B^†)(I_n\otimes K_{qm}\otimes I_p)(\mathit{\text{vec}}(A)\otimes I_{pq})$.

Proof. When $\|\Delta A\|_2$ is sufficiently small, we may assume that $\|A^† \Delta A\|_2 < 1$. Then, from Lemmas 2 and 3 with $R(\Delta A)\subseteq R(A)$, $R((\Delta A)^T)\subseteq R(A^T)$, neglecting the second-order terms gives

Similarly, we have $(B+\Delta B)^† = B^†-B^†\Delta BB^†$ when $\|\Delta B\|_2$ is sufficiently small and $\Delta B\in \mathcal{T}$. Thus, for small $\Delta A$ and $\Delta B$, the linear term in $\Delta x = \left((A+\Delta A)^†\otimes (B+\Delta B)^†\right)(b+\Delta b)-(A^†\otimes B^†)b$ is

Applying the operator vec to (2.2) and using Lemma 1.1, we have

Consequently, we have

Since $(A^†\otimes B^†)\Delta b-(A^†\otimes B^†)\left(A\otimes \Delta B+\Delta A\otimes B\right)x_{_{LS}}$ is the linear term in $\Delta x$, Theorem 3.1 holds.

The formula for $\kappa^{(\mathcal{F})}(A, B, b)^{\text{upper1}}$ in Theorem 2.1 involve the permutation matrix $K_{qm}$ and Kronecker products, which make them inefficient for computation. In order to overcome this shortcoming, the next corollary will provide easily computable upper bound.

Corollary 2.1. For the estimate $\kappa^{(\mathcal{F})}(A, B, b)^{\mathit{\text{upper1}}}$ in Theorem 2.1, we have

Proof. It follows from Lemma 1.1 that

which together with Theorem 2.1 complete the proof of this corollary.

The normwise condition number under the weighted $2$-norm is given in the following theorem.

Theorem 2.2. When $A$ and $B$ are of rank deficient, the condition number

satisfies

Proof. By taking the $2$-norm of (2.2) and using Lemma 1.1, we obtain

which together with the definition of $\kappa^{(\mathcal{2})}(A, B, b)$ complete the proof of this theorem.

We now give the upper bound estimates of the normwise condition numbers for the LS problem (1.1) under the weighted Frobenius norm and weighted $2$-norm when only $A$ and $b$ are perturbed. These results can be proved in the same manners as in Theorems 2.1 and 2.2, and hence, we state them in the following theorem without their proofs.

Theorem 2.3. When $A$ is of rank deficient, we have

and

where $P = (x_{_{LS}}^T\otimes A^†\otimes B^†)(I_n\otimes K_{qm}\otimes I_p)(I_{mn}\otimes\mathit{\text{vec}}(B))$ and

When $B = 1$, the problem (1.1) reduces to the classical LS problem $\min\limits_{x\in \mathbb{R}^{n}}\|Ax-b\|_2$. When $B = 1$, it follows from Theorem 2.3 that

The upper bound estimate in the above inequality was proved to be the exact expression of $\kappa^{(\mathcal{F})}(A, b)$ in [21,Corollary 2.2]. Therefore, we conjecture that the upper bound estimates in Theorem 2.1, Theorem 2.2 and Theorem 2.3 are the exact expression of the corresponding normwise condition numbers. This needs to be further studied in the future.

3.   Mixed and componentwise condition numbers

The normwise condition number measures both the input and output data errors by norms. Norms can tell us the overall size of a perturbation but not how that size is distributed among the elements it perturbs, and this information can be important when the data is badly scaled or contains many zeros ^[20]. To take into account the relative of each data component, and, in particular, a possible data sparseness, componentwise condition numbers have been increasingly considered. These are mostly of two kinds: mixed and componentwise. The terminologies of mixed and componentwise condition numbers may be first used by Gohberg and Koltracht ^[11]. We adopt their terminology and define the mixed and componentwise condition numbers for the LS problem (1.1) are defined as follows:

and

We assume that $x_{_{LS}}\neq 0$ for $m(A, B, b)$ and $x_{_{LS}}$ has no zero entries for $c(A, B, b)$.

The following theorem gives the upper bounds for the mixed and componentwise condition numbers of the LS problem (1.1).

Theorem 3.1. When $A$ and $B$ are of rank deficient, we have

and

where $P = (x_{_{LS}}^T\otimes A^†\otimes B^†)(I_n\otimes K_{qm}\otimes I_p)(I_{mn}\otimes\mathit{\text{vec}}(B))$ and $Q = (x_{_{LS}}^T\otimes A^†\otimes B^†)(I_n\otimes K_{qm}\otimes I_p)(\mathit{\text{vec}}(A)\otimes I_{pq})$.

Proof. According to $|\Delta A|\leq \epsilon|A|$, we know that the zero elements of $A$ are not permitted to be perturbed. Therefore,

where $D_A = \text{diag}(\text{vec}(A))$. Similarly, we have $\text{vec}(\Delta B) = D_BD_B^† \text{vec}(\Delta B)$ and $\Delta b = D_bD_b^† \Delta b$ with $D_B = \text{diag}(\text{vec}(B))$ and $D_b = \text{diag}(b)$. Thus the linear term $(A^†\otimes B^†)\Delta b-(A^†\otimes B^†)\left(A\otimes \Delta B+\Delta A\otimes B\right)x_{_{LS}}$ of $\Delta x$ can be rewritten as

Taking the infinity norm and using the assumption $|\Delta A|\leq \varepsilon|A|$, $|\Delta B|\leq \varepsilon|B|$ and $|\Delta b|\leq \varepsilon|b|$, we have

Since $(A^†\otimes B^†)\Delta b-(A^†\otimes B^†)\left(A\otimes \Delta B+\Delta A\otimes B\right)x_{_{LS}}$ is the linear term of $\Delta x$, $m(A, B, b)$ is bounded by

where $e$ is an $mn+mp+pq$ dimensional vector with all entries equal to one.

Recall that in the definition of $c(A, B, b)$, we assume that $x_{_{LS}}$ has no zero entries. Hence, it follows from (3.1) and the assumption $|\Delta A|\leq \varepsilon|A|$, $|\Delta B|\leq \varepsilon|B|$ and $|\Delta b|\leq \varepsilon|b|$ that

where $D_{x_{_{LS}}} = \text{diag}(\text{vec}(x_{_{LS}}))$. Hence, we have

Using Lemma 1.1, we can get

Similarly, we can deduce that

Because of the monotonicity property of the infinity norm, the upper bounds $m(A, B, b)^{\text{upper2}}$ and $c(A, B, b)^{\text{upper2}}$ can be obtained by applying the aforementioned two inequalities to $m(A, B, b)^{\text{upper1}}$ and $c(A, B, b)^{\text{upper1}}$ and by using the matrix norm triangular inequality.

The following theorem gives the upper bound estimates of the mixed and componentwise condition numbers for the LS problem (1.1) when only $A$ and $b$ are perturbed, which can be proved in the same way as Theorem 3.1.

Theorem 3.2. When $A$ is of rank deficient, we have

and

where $P = (x_{_{LS}}^T\otimes A^†\otimes B^†)(I_n\otimes K_{qm}\otimes I_p)(I_{mn}\otimes\mathit{\text{vec}}(B))$.

When $B = 1$, it follows from Theorem 3.2 that

and

which have been obtained in ^[16].

4.   Numerical experiments

We consider the LS problem (1.1) with

We first compare $\kappa^{(\mathcal{F})}(A, B, b)^{\text{upper1}}$, $\kappa^{(\mathcal{F})}(A, B, b)^{\text{upper2}}$, $\kappa^{(\mathcal{2})}(A, B, b)^{\text{upper2}}$ with the upper bounds of the mixed and componentwise condition numbers given in Theorem 3.1. Thus, upon computations in MATLAB R2015b with precision $2.2204\times 10^{-16}$, we get the results listed in Table 1. From Table 1, we find that as the $(1, 1)$-element of $A$ increases, the upper bounds of the normwise condition numbers become larger and larger, while, comparatively, the upper bounds of the mixed and componentwise condition numbers have no change. This is mainly because the mixed and componentwise condition numbers notice the structure of the coefficient matrix $A$ with respect to scaling, but the normwise condition numbers ignore it.

For $i = 0$, suppose the perturbations are $\Delta A = 10^{-j}\times A, \; \Delta B = 10^{-j}\times B$ and $\Delta B = 10^{-j}\times\text{rand}(9, 1)$, where $\text{rand}(\cdot)$ is the MATLAB function. Obviously, $\Delta A\in\mathcal{S}$ and $\Delta B\in\mathcal{T}$. Define $\varepsilon_1 = \frac{\left\|(\Delta A, \Delta B, \Delta b)\right\|_{\mathcal{F}}}{\left\|(A, B, b)\right\|_{\mathcal{F}}}$, $\varepsilon_2 = \frac{\left\|(\Delta A, \Delta B, \Delta b)\right\|_{\mathcal{2}}}{\left\|(A, B, b)\right\|_{\mathcal{2}}}$ and $\varepsilon_3 = \max\{\varepsilon:\; |\Delta A|\leq \varepsilon|A|, \; |\Delta B|\leq \varepsilon|B|\; |\Delta b|\leq \varepsilon|b|\}$, it follows from the definitions of $\kappa^{(\mathcal{F})}(A, B, b)$, $\kappa^{(\mathcal{2})}(A, B, b)$, $m(A, B, b)$ and $c(A, B, b)$ that

and

for small $\varepsilon_1$, $\varepsilon_2$ and $\varepsilon_3$. As shown in Table 2, the error bounds given by the upper bounds of the condition numbers are at most two order of magnitude larger than the actual errors. This illustrates that, the estimates $\kappa^{(\mathcal{F})}(A, B, b)^{\text{upper1}}$, $\kappa^{(\mathcal{2})}(A, B, b)^{\text{upper}}$, $m(A, B, b)^{\text{upper1}}$ and $c(A, B, b)^{\text{upper1}}$ can estimate their corresponding condition numbers well.

Acknowledgments

This work was supported by the Foundation for Distinguished Young Scholars of Gansu Province (Grant No.20JR5RA540).

Conflict of interest

The authors declare there is no conflict of interest.