Structured conditioning theory for the total least squares problem with linear equality constraint and their estimation

1.   Introduction

The total least squares with linear equality constraint (TLSE) problem is stated as

where $\mathcal{Q} \in \mathbb{R}^{p \times n}$ and $\left[\begin{array}{c}\mathcal{Q} \\ \mathcal{A}\end{array}\right]$ are full row-rank and full column rank, respectively such that $\mathcal{A} \in \mathbb{R}^{q \times n}$, $\mathbf{b} \in \mathbb{R}^{q}$ and $\mathbf{d}\in \mathbb{R}^{p}$. As proved in Eq (17) in ^[1], if the following genericity condition holds

then the TLSE problem guarantees the existence of the unique solution

where

The TLSE problem is reduced to the total least squares (TLS) problem ^[2,3] when $\mathcal{Q} = 0$ and $\mathbf{d} = 0$, to the least squares problem with equality constraint ^[4,5,6,7,8] when $G = 0$, and to the mixed least squares-total least squares problem ^[3,9] when $\mathcal{Q} = 0$ and $\mathbf{d} = 0$, and some columns of $G$ are zero. The TLSE problem was first demonstrated by Dowling et al. ^[10] in 1992. They introduced the TLSE problem and interpreted how to solve it by using SVD and QR matrix factorizations, whereas Schaffrin and felus ^[11,12] investigated an iterative method of constrained total least squares estimation and an algorithmic approach to the TLSE problem with linear and quadratic constraints by using the Euler-Lagrange theorem. Liu et al. ^[13] suggested a QR-based inverse iteration method. Liu and colleagues ^[1,14] presented the perturbation analysis and condition numbers of the TLSE problem.

Condition numbers play a vital role in estimating forward errors of the algorithms ^[15,16,17]. Recent studies of condition numbers for different problems such as TLS, TLSE, multidimensional, mixed least squares, truncated and scaled TLS problems can be found in ^{[1,14,18,19,20,21,22,23,24]}. Structured TLS problems have received significant attention in recent years (see ^[25,26,27]). This topic has shifted many authors attention toward research on the structured condition numbers in which the TLS problem ^[28,29], the truncated TLS problem ^[30], the scaled TLS problem ^[31] and the mixed LS-TLS problem ^[32] are included. The analysis of the structured perturbations on the input data is essential for structured TLS problems because studying the structured TLSE problem is motivated by the fact that these methods preserve the underlying matrix structure that can improve the accuracy and efficiency of computation.

As far as we know, no work has been done on structured condition numbers for the TLSE problem. So, the main purpose of this work is to study structured condition numbers for TLSE problems as well as their relationships to unstructured condition numbers, and their statistical estimation. In certain situations, the computation of unstructured and structured condition numbers is not directly applicable to analyzing the forward error bound, but studying a reliable statistical condition estimation for unstructured and structured condition numbers is attractive and interesting.

Particularly, we will derive the unstructured condition numbers for a linear function of the TLSE problem by using the dual technique in Section 3. The dual technique was first introduced in ^[33] for the mixed and componentwise condition numbers of the least squares problem. Later, it was applied to get the mixed and componentwise condition numbers of the total least squares problem ^[28], the weighted least squares problem ^[34] and the constrained and weighted least squares problem ^[35]. As described in ^[33], the dual technique allows us to derive condition numbers by maximizing a linear function over a space of smaller dimension than the data space. Furthermore, in Section 4, the explicit expressions of relevant structured condition numbers are provided, and the links between the unstructured condition numbers for the TLSE problem and their corresponding structured counterparts are investigated. We also discuss how to recover the expressions of structured condition numbers for the solution of the TLS problem with the help of the derivative of the TLSE problem. Considering that it is expensive to compute these condition numbers, we consider the statistical estimation of both structured and unstructured condition numbers by using the small-sample statistical condition estimation (SSCE) method ^[36] and design three algorithms in Section 5. Meanwhile, in Section 5, we also provide some numerical findings and demonstrate the accuracy of the proposed algorithms by considering numerical examples. Moreover, Section 2 describes some useful preliminaries, and Section 6 gives some brief conclusions.

2.   Basic notations

In this section, we recall some necessary definitions and results about Dual techniques, which will be used throughout the paper.

2.1.   Dual techniques

Consider a linear operator $\mathcal{J}: \mathbb{X} \rightarrow \mathbb{Y}$, between two Euclidean spaces $\mathbb{X}$ and $\mathbb{Y}$ with the scalar products $\langle\cdot, \cdot\rangle_{\mathbb{X}}$ and $\langle\cdot, \cdot\rangle_{\mathbb{Y}}$, respectively. Denote the corresponding norms by $\|\cdot\|_{\mathbb{X}}$ and $\|\cdot\|_{\mathbb{Y}}$, respectively. Here we provide definitions for "adjoint operator" and "dual norm".

Definition 2.1. The adjoint operator of $\mathcal{J}, \mathcal{J}^{*}: \mathbb{Y} \rightarrow \mathbb{X}$ is expressed as follows:

where $(\mathbf{x}, \mathbf{y}) \in \mathbb{X} \times \mathbb{Y}$.

Definition 2.2. The dual norm $\|\cdot\|_{\mathbb{X}^{*}}$ of $\|\cdot\|_{\mathbb{X}}$ is

It is known that the dual norms of the standard vector norms for the canonical scalar product in $\mathbb{R}^{n}$ are provided by:

Considering the scalar product $< A, B > = \mathrm{trace}(A^{T}B)$, the norm of a matrix in $\mathbb{R}^{m\times n}$ is $\|A\|_{F^{\ast}} = \|A\|_{F}$.

Suppose that $\|\cdot\|_{\mathbb{X}, \mathbb{Y}}$ is an operator norm induced by $\|\cdot\|_{\mathbb{X}}$ and $\|\cdot\|_{\mathbb{Y}}$ for the linear operator $\mathcal{J}$ from $\mathbb{X}$ to $\mathbb{Y}$. Assume that $\|\cdot\|_{\mathbb{Y}^{\ast}, \mathbb{X}^{\ast}}$ is an operator norm induced by dual norms $\|\cdot\|_{\mathbb{X}^{\ast}}$ and $\|\cdot\|_{\mathbb{Y}^{\ast}}$ for the linear operator from $\mathbb{Y}$ to $\mathbb{X}$.

The above discussion implies the following results ^[33].

Lemma 2.3. Assume that $\mathcal{J}$ is a linear operator from $\mathbb{X}$ to $\mathbb{Y}$; then,

If the Euclidean space $\mathbb{Y}^{\ast}$ has fewer dimensions than $\mathbb{X}$, then it will be very suitable to find $\|\mathcal{J}^{\ast}\|_{\mathbb{Y}^{\ast}, \mathbb{X}^{\ast}}$ in place of $\|\mathcal{J}\|_{\mathbb{X}, \mathbb{Y}}$ as given in ^[33].

According to ^[15], the absolute condition number of $\varphi$ at $\mathbf{y}\in \mathbb{X}$ is defined as

where $\varphi$ is Fréchet differentiable in the neighborhood of $\mathbf{y}\in \mathbb{X}$ and ${\rm{d}}\varphi(\mathbf{y})$ presents the Fréchet differential of $\varphi$ at $\mathbf{y}$. The relative normwise condition number for nonzero $\varphi$ is given by

By using Lemma 2.3, we can define $\kappa$ in terms of an adjoint operator and a dual norm as follows:

Let $\mathbb{X} = \mathbb{R}^{n}$ be a data space for the componentwise metric and $\mathbb{X}_{\mathbf{y}}$ presents the subset of all elements ${\rm{d}}\mathbf{y}\in \mathbb{R}^{n}$ for any input data $\mathbf{y}\in \mathbb{R}^{n}$ satisfying ${\rm{d}}\mathbf{y}_{i} = 0$ for $\mathbf{y}_{i} = 0, 1\leq i \leq n$. Thus, the perturbation ${\rm{d}}\mathbf{y} \in \mathbb{X}_{\mathbf{y}}$ of $\mathbf{y}$ can be measured by applying the below componentwise norm with respect to $\mathbf{y}$ as follows:

Equivalently,

By Eq (2.16) in ^[28], the dual norm of (2.4) can be written as

Using the above componentwise norm, we can rewrite the condition number $\kappa$.

Lemma 2.4. ^[28,33] Given the above assumptions and the componentwise norm defined in (2.4), the condition number $\kappa$ can be expressed as

where $\|\cdot\|_{c^{\ast}}$ is given by (2.5).

Next, we present some necessary results for the TLSE problem, which will be used throughout the paper.

Lemma 2.5. Let

Consider the following linear function $\varphi$ of the TLSE solution:

where $\mathcal{L}\in \mathbb{R}^{l \times n}$. With the help of [14,Theorem 3.2], using the genericity assumption (1.2) implies that $\varphi: \mathbb{R}^{m \times n} \times \mathbb{R}^{m \times 1}$ is a continuous map. Further, $\varphi$ is Fréchet differentiable at $(\mathcal{K}, f)$; its Fréchet derivative is

where $\mathrm{d} \mathcal{K} \in \mathbb{R}^{m \times n}$, $\mathrm{d} f \in \mathbb{R}^{m \times 1}$, $t^{T} = r^{T}\big[-\big(\tilde{\mathcal{A}} \tilde{\mathcal{Q}}^{\dagger}\big), \quad I_{q}\big]$ and $r = \mathcal{A} x-\mathbf{b}.$

Using the 'vec' operator and applying $\rm{vec}(AXB) = (B^{T}\otimes A)\rm{vec}(X)$, we obtain

where

Using (2.3) and (2.8), the absolute normwise condition number of $\varphi$ for the TLSE solution can be expressed as follows:

The relative normwise condition number corresponding to $\kappa(\mathcal{K}, f)$ is given by

3.   Unstructured condition number of TLSE problem

When the data are sparse or poorly scaled, the componentwise perturbation analysis is more appropriate for investigating the TLSE problem's conditioning. Through the use of dual techniques discussed in the previous part, we will derive the explicit expressions of unstructured mixed and componentwise condition numbers for the TLSE problem in this section. Additionally, we demonstrate the mathematical equality between the derived expressions and the earlier ones ^[1]. Before moving on to the main results, we will first provide the lemma, which is as follows:

Lemma 3.1. The adjoint operator of the Fréchet derivative $\aleph(\mathrm{d} \mathcal{K}, \mathrm{\; d} f)$ in (2.7) is given by

Proof. Let $\aleph_{1}(u)$ and $\aleph_{2}(u)$ be the first and second terms in the sum (2.7), respectively. For any $u \in \mathbb{R}^{l}$, we get the following expression by using the concept of the scalar product in the matrix space:

For $\aleph_{2}$, we have

Let

then

which completes the proof. Now, we present an explicit expression of the condition number $\kappa$ (2.3) by applying the dual norm in the solution space.

Theorem 3.2. The condition number (2.3) for the linear function $\varphi$ of the TLSE solution is expressed as

where

and $D_{X}$ presents the diagonal matrix $\rm{diag}(\rm{vec}(X))$ for any matrix $X$.

Proof. Let $\mathrm{d} k_{i j}$ and $\mathrm{d} f_{i}$ be the entries of $\mathrm{d} \mathcal{K}$ and $\mathrm{d} f$, respectively. Thus, using (2.5), we obtain

Using Lemma 3.1, we get the following:

where $t_{j}$ is the jth component of $t$. Consider (3.1), it can be verified that $x_{j}\left(2\|r\|_{2}^{-2} \mathcal{H}\mathcal{A}^{T} r t^{T}-\right.$ $\left.\left[\mathcal{Q}_{\mathcal{A}}^{\dagger}, \mathcal{H \mathcal{A}}^{T}\right]\right) e_{i}-t_{i} \mathcal{H}^{T} e_{j}$ is the $(m(j-1)+i)$th column of the $n \times(m n)$ matrix $\mathcal{V}$. Thus, the above expression equals

Then, by Lemma 2.4, we get the required result.

Using Theorem 3.2, we can easily obtain the explicit expressions of the mixed condition number for the linear function $\varphi$ of the TLSE solution.

Corollary 3.3. When the infinite norm is taken as the norm in the solution space $\mathbb{Y}$ under the same assumption as in Theorem 3.2, then obtain

If the infinity norm is selected as the norm in the solution space $\mathbb{R}^{n}$, the corresponding mixed condition number is given by

Using Theorem 3.2, we can also find the explicit expressions of the componentwise condition number for the linear function $\varphi$ of the TLSE solution.

Corollary 3.4. Considering the componentwise norm on the solution space given by

The componentwise condition number for the linear function $\varphi$ of the TLSE solution has the following expression:

By applying the 2-norm to the solution space, we get an upper bound for the relevant condition number in terms of the 2-norm.

Corollary 3.5. When the 2-norm is used in the solution space, we obtain

Proof. If $\|\cdot\|_{\mathbb{Q}} = \|\cdot\|_{2}$, then $\|\cdot\|_{\mathbb{Q}}^{*} = \|\cdot\|_{2}$. Utilizing Theorem 3.2, we obtain the following

According to ^[37], for any matrix $W$, $\|W\|_{2, 1} = \max _{\|u\|_{2} = 1} \|W u\|_{1} = \|W \hat{u}\|_{1}$, where $\hat{u} \in \mathbb{R}^{l}$ is a unit 2-norm vector. Using $\|\hat{u}\|_{1} \leq \sqrt{k}\|\hat{u}\|_{2}$, we get

Substituting the above $W$ with $\left[\mathcal{V} D_{\mathcal{K}}, \mathcal{S D}_{f}\right]^{T} \mathcal{L}^{T}$, we have

which implies (3.5).

Additionally, we utilize the dual techniques to derive the condition number expressions, which allows us to minimize the computational complexity of the problem. This is possible due to the fact that the number of columns in the matrix expression of $\aleph$ is often less than the number of rows.

Remark 3.6. Using the Kronecker product property and the fact that

as shown in Eq (3.3) ^[14], we have

Applying these two facts together with (3.2) and (3.4) for the case where $\mathcal{L} = I_{n}$ allows us to recover the expressions of normwise, mixed and componentwise condition numbers of the TLSE problem, which are given in [1,Theorem 5].

The following corollary, based on a triangle inequality, yields the upper bounds for $\kappa_{m}$ and $\kappa_{c}$, without the Kronecker product, and it omits its proof. Note that the following relationship holds for any matrix $W\in \mathbb{R}^{p \times q}$ and diagonal matrix $D_{v} \in \mathbb{R}^{q \times q}$: $\left\|W D_{v}\right\|_{\infty} = \left\|\left|W D_{v}\right|\right\|_{\infty} = \left\||W|\left|D_{v}\right|\right\|_{\infty} = \||W|\| D_{v}\left|e\left\|_{\infty} = \right\|\right| W\left\|D_{v}\left|\left\|_{\infty} = \right\|\right| W\right\| v \mid \|_{\infty}$, where $e = [1, \ldots, 1] \in \mathbb{R}^{q}$.

Corollary 3.7. The mixed and componentwise condition numbers for the linear function $\varphi$ of the TLSE solution can be bounded as follows:

4.   Structured condition numbers of TLSE problem

In this section, we study the sensitivity of a linear function of the structured TLSE solution to perturbations on the data $k$ and $f$, which is given below:

such that $\varphi_{s}\left(k, f\right) = \mathcal{L}x = \mathcal{L} \big(\mathcal{Q}^{\dagger}_{\mathcal{A}} b+\mathcal{H \mathcal{A}}^{T} d\big)$ and $x$ is the solution of the structured TLSE problem. Assume that $\mathcal{K} \in S$ is a linear structured matrix, like a Toeplitz matrix for the structured TLSE problem, where the set $S$ of the linear structured matrix has the dimension $\theta$ and there exists a unique vector denoted by $k = \left[k_{1}, \ldots, k_{\theta}\right]^{T}$ such that

where $S_{1}, \ldots, S_{\theta}$ form a basis of $S$. Note that

and

where $\Phi_{\mathcal{K}}^{\text {s }} = \left[\operatorname{vec}\left(S_{1}\right), \operatorname{vec}\left(S_{2}\right), \cdots, \operatorname{vec}\left(S_{\theta}\right)\right]$ and by the statement in [31,Theotrem 4.1], $\Phi_{\mathcal{K}}^{\text {s}}$ is orthogonal with full column rank and has one nonzero entry in each row at most. Consider the fact that

when we restrict the perturbation matrices $[\Delta \mathcal{K}, \Delta f]$ into $[\mathcal{K}, f]$, i.e., $\operatorname{vec}([\Delta \mathcal{K}, \Delta f]) = \Phi_{\mathcal{K}, f}^{\text {s }} \epsilon$, where $\epsilon \in \mathbb{R}^{\theta+m}$.

The following structured absolute normwise condition number of $\varphi_{s}$ can be obtained by using (2.3) and (2.8)

where

The structured relative normwise condition number corresponding to $\kappa_{s}(k, f)$ is expressed as

which can be efficiently computable with less storage and it is Kronecker product-free.

With the help of (2.7), we have to prove that $\varphi_{s}$ given in (4.1) is Fréchet differentiable at $(k, f)$ and find its Fréchet derivative.

Lemma 4.1. Assume the following linear function $\varphi_{s}$ of the TLSE solution

where $L \in \mathbb{R}^{l \times n}$. With the help of [14,Theorem 3.2], using the genericity assumption (1.2) implies that $\varphi_{s}: \mathbb{R}^{\theta} \times \mathbb{R}^{m}$ is a continuous map. Further, $\varphi_{s}$ is Fréchet differentiable at $(\mathcal{K}, f)$; its Fréchet derivative is

where $U = \left[u_{1}, \ \ \ldots, u_{\theta}\right] \in \mathbb{R}^{n \times \theta}, \ \ u_{i} = \left(2\|r\|_{2}^{-2} \mathcal{H}\mathcal{A}^{T} r t^{T}-\left[\mathcal{Q}_{\mathcal{A}}^{\dagger}, \mathcal{H \mathcal{A}}^{T}\right]\right) S_{i} x-\mathcal{H S}_{i}^{T} t, \\ \mathrm{\; d} k \in \mathbb{R}^{\theta}$ and $\mathrm{d} f \in \mathbb{R}^{m}.$

Lemma 4.2. The adjoint operator of the Fréchet derivative $\aleph_{s}(\mathrm{\; d} k, \mathrm{\; d} f)$ in (4.4) is given by

Theorem 4.3. The condition number of the linear function $\varphi_{s}$ for the structured TLSE problem can be deduced from (3.1) as follows:

where

With the help of Theorem 4.3, we can simply determine the structured mixed condition number for the linear function $\varphi_{s}$ of the TLSE solution.

Corollary 4.4. When the infinite norm is taken as the norm in the solution space $\mathbb{Y}$, under the same assumption as in Theorem 4.3, we get

If the infinity norm is selected as the norm in the solution space $\mathbb{R}^{n}$, the corresponding structured mixed condition number is given by

In light of the 2-norm to the solution space, we will derive an upper bound for the associated structured condition number in terms of the 2-norm. Since the proof is similar to that of Corollary 3.5, we will not repeat it here.

Corollary 4.5. When the 2-norm is used in the solution space, we get

Corollary 4.6. Assume that (3.3) represents the componentwise norm in the solution space. The structured componentwise condition number for the linear function $\varphi_{s}$ of the TLSE solution has the following two expressions:

For a linearly structured matrix given by (4.2), we verify that the structured absolute normwise $\kappa_{s}(k, f)$, mixed $\kappa_{s, m}(k, f)$ and componentwise condition numbers $\kappa_{s, c}(k, f)$ are less than the unstructured condition numbers $\kappa_{n}(\mathcal{K}, f)$, $\kappa_{m}(\mathcal{K}, f)$ and $\kappa_{c}(\mathcal{K}, f)$ respectively.

Theorem 4.7. Using the notations above, we have that $\kappa_{s}(k, f) \leq \kappa(\mathcal{K}, f)$. Moreover suppose that the basis $\left\{S_{1}, S_{2}, \ldots, S_{\theta}\right\}$ for $\mathcal{S}$ satisfies $|\mathcal{K}| = \sum_{i = 1}^{\theta}\left|k_{i}\right|\left|S_{i}\right|$ for any $\mathcal{K} \in \mathcal{S}$; then,

Proof. The matrix $\Phi_{\mathcal{K}}^{\text {s}}$ is column orthogonal according to [31,Theorem 4.1]. Therefore, $\|\Phi_{\mathcal{K}}^{\text {s}}\|_{2} = 1$ and it is simple to observe that $\kappa_{s}(k, f) \leq \kappa(\mathcal{K}, f)$ by comparing their expressions. By applying monotonicity of the infinity norm and using the assumption that

we get the following result.

Similarly, we can prove that $\kappa_{s, c} (k, f) \leq \kappa_{c} (\mathcal{K}, f)$.

Remark 4.8. By utilizing the intermediate results of Lemma 4.1, we can retrieve the structured condition numbers for the TLS problem ^[28]. Suppose that $\mathcal{Q} = \Delta \mathcal{Q} = 0$ and $\mathbf{d} = \Delta \mathbf{d} = 0$; we have

$2\|r\|_{2}^{-2}\mathcal{A}^{T}rr^{T} = -\frac{2x\bar{r}^{T}}{1+xx^{T}}$ and

Considering the above fact and using (4.4), we obtain

$\bar{U} = \left[\bar{u}_{1}, \ \ \ldots, \bar{u}_{\theta}\right] \in \mathbb{R}^{n \times \theta}, \ \ \bar{u}_{i} = -\big(\mathcal{A}^{T}+\frac{2x\bar{r}^{T}}{1+xx^{T}}\big) S_{i} x+\mathcal{S}_{i}^{T} \bar{r}$, $\mathrm{\; d} a \in \mathbb{R}^{\theta}$ and $\mathrm{d}b \in \mathbb{R}^{m},$ where the latter is just the result in [28,Lemma 3.2] with which we can recover the structured condition numbers for the TLS problem ^[28].

5.   Numerical experiments

In the following section, we continue our research on estimating the unstructured and structured condition numbers for the TLSE problem before presenting the specific examples. In this part, we construct two algorithms to estimate the unstructured condition numbers. The first one, outlined in Algorithm A, is from ^[36] and has been used for different matrix problems ^{[29,30,38,39,40,41,42]}. We propose an algorithm for the unstructured normwise condition estimation of the TLSE problem based on SSCE. The second one, outlined in Algorithm B, is also from ^[36]. We provide a statistical estimation of the unstructured mixed and componentwise condition numbers by using the SSCE method ^[36].

Denote by ${\kappa^{\mathrm{TLSE}}_{i}}(\mathcal{A}, d)$ the normwise condition number of the function $z^{T}_{i}x$, where $z_{i}$'s are from the unit $n$-sphere $S_{n-1}$ and are orthogonal. From (2.9), we have

where

The analysis in ^[36] shows that

where $N_{\mathrm{SCE}}^{\mathrm{TLSE}, (\gamma)}: = \frac{\omega_{\gamma}}{\omega_{\beta}} \sqrt{\left\|\sigma_{1}\right\|_{2}^{2}+\left\|\sigma_{2}\right\|_{2}^{2}+\cdots+\left\|\sigma_{\gamma}\right\|_{2}^{2}} = \left\|\kappa_{\mathrm{abs}}^{\mathrm{TLSE}, (\gamma)}\right\|_{F}$ is a good estimate of the normwise condition number (2.9). In the above expression, $\omega_{\beta}$ is the Wallis factor with $\omega_{1} = 1$, $\omega_{2} = 2 / \pi$, and for $\beta > 2$;

The Wallis factor can be approximated by

with high accuracy. As a matter of fact, we can devise Algorithm A.

Algorithm A (SSCE method for the unstructured normwise condition number)

$(1)$ Generate matrices $\left[\Delta \mathcal{K}_{1}, \Delta f_{1}\right], \ldots, \left[\Delta \mathcal{K}_{\gamma}, \quad \Delta f_{\gamma}\right]$ with each entry in $\mathcal{N}(0, 1),$ and orthonormalize the matrix

to obtain $\left[\tau_{1}, \tau_{2}, \ldots, \tau_{\gamma}\right]$ via the modified Gram-Schmidt orthogonalization process. Each $\tau_{i}$ can be converted into the corresponding matrices $\left[\Delta \mathcal{K}_{i}, \Delta f_{i}\right]$ by applying the unvec operation.

$(2)$ Let $\beta = m+m n$. Approximate $\omega_{\beta}$ and $\omega_{\gamma}$ by using (5.3).

$(3)$ For $i = 1, 2, \ldots, \gamma,$ compute

$(4)$ Compute the absolute condition vector by using (5.1), where the square operation is applied to each entry of $\sigma_{i}, i = 1, 2, \ldots, \gamma$ and the square root is also applied componentwise.

$(5)$ Estimate the normwise condition number (2.9) by using (5.2).

Algorithm B (SSCE method for the unstructured mixed and componentwise condition numbers)

$(1)$ Generate matrices $\left[\Delta \mathcal{K}_{1}, \Delta f_{1}\right], \left[\Delta \mathcal{K}_{2}, \Delta f_{2}\right], \ldots, \left[\Delta \mathcal{K}_{\gamma}, \Delta f_{\gamma}\right]$ with each entry in $\mathcal{N}(0, 1)$ and orthonormalize the matrix

to obtain $\left[\tau_{1}, \tau_{2}, \ldots, \tau_{\gamma}\right]$ via the modified Gram-Schmidt orthogonalization process. Apply the unvec operation to convert each $\tau_{i}$ into the corresponding matrices $\left[\Delta \mathcal{K}_{i}, \Delta f_{i}\right]$. Suppose that $\left[\Delta \mathcal{K}_{i}, \Delta f_{i}\right]$ is the matrix $\left[\widetilde{\Delta \mathcal{K}}_{i}, \widetilde{\Delta f_{i}}\right]$ and is multiplied by $[\mathcal{K}, f]$ componentwise.

$(2)$ Assume that $\beta = m(n+1)$. Approximate $\omega_{\beta}$ and $\omega_{\gamma}$ by using (5.3).

$(3)$ For $i = 1, 2, \ldots, \gamma,$ compute

Using the approximations for $\omega_{\beta}$ and $\omega_{\gamma},$ compute the absolute condition vector

$(4)$ Compute the relative condition vector $C_{\mathrm{rel}}^{\mathrm{TLSE}, (\gamma)} = C_{\mathrm{abs}}^{\mathrm{TLSE}, (\gamma)} / x.$ Estimate the mixed and componentwise condition estimations $m_{\mathrm{SCE}}^{\mathrm{TLSE}, (\gamma)}$ and $c_{\mathrm{SCE}}^{\mathrm{TLSE}, (\gamma)}$ as follows:

On the basis of the SSCE method ^[36], we propose Algorithm C to estimate the structured normwise, mixed and componentwise condition numbers.

Algorithm C (SSCE method for the structured condition numbers)

$(1)$ Generate matrices $\left[\Delta k_{1}, \Delta k_{2}, \ldots, \Delta k_{\gamma}\right] and \left[\Delta f_{1}, \Delta f_{2}, \ldots, \Delta f_{\gamma}\right]$ with entries in $\mathcal{N}(0, 1),$ where $k_{i} \in \mathbb{R}^{\theta}$ and $f_{i} \in \mathbb{R}^{m}.$ Orthonormalize the below matrix

to get an orthonormal matrix $\left[\xi_{1}, \xi_{2} \ldots, \xi_{\gamma}\right]$ by using a modified Gram-Schmidt orthogonalization technique, where $\xi_{i}$ can be converted into the corresponding matrices $\left[k_{i}^{\top}, f_{i}^{\top}\right]^{\top}$ by applying the unvec operation.

$(2)$ Let $\alpha = q+m$. Approximate $\omega_{\alpha}$ and $\omega_{\gamma}$ by using (5.3).

$(3)$ For $j = 1, 2, \ldots, \gamma,$ compute $y_{j}$ from (5.4). Estimate the absolute condition vector

$(4)$ Estimate the structured normwise condition estimation as follows:

$(5)$ Compute the structured mixed condition estimation $m_{\mathrm{SCE}}^{\mathrm{STLSE}, (\gamma)}$ and structured componentwise condition estimation $c_{\mathrm{SCE}}^{\mathrm{STLSE}, (\gamma)}$ as follows:

Moving forward, we will illustrate four specific examples. The first compares the unstructured condition numbers with our SSCE-based estimates. It also comes to a conclusion about how well Algorithms A and B make estimates that are too high. The second is used to present the efficiency of statistical condition estimators of structured normwise, mixed, and componentwise condition numbers, while the third compares the structured and unstructured condition numbers, and the fourth checks the efficiency of over estimation ratios by implementing Algorithm C in in association with the structured condition numbers.

Example 5.1. To compare the unstructured normwise, mixed and componentwise condition numbers and interpret the effectiveness of Algorithms A and B, we employ the random TLSE problem that is generated by following method given in ^[18]. Consider a random matrix $[\mathcal{A}, \mathbf{b}]$, and the matrix $\widetilde{\mathcal{Q}} = [\mathcal{Q}, \mathbf{d}]$ is constructed as follows

where $Y = I_{p}-2 y y^{T}, Z = I_{n+1}-2 z z^{T},$ and $y \in \mathbb{R}^{\gamma}, z \in \mathbb{R}^{n+1}$ are random unit vectors, and $D$ denotes the diagonal matrix of order $p \times p$ with a condition number of $\kappa_{\widetilde{\mathcal{Q}}}$. For Algorithms A and B, we assume $q = 300$, $p = 75$ and $n = 225$, we create various TLSE problems for every chosen $\kappa_{\widetilde{\mathcal{Q}}}$. The matrix $\mathcal{L}$ is provided for the purpose of selecting the component part of the solution. For instance, when $\mathcal{L} = I_{n}$ $(l = n)$, all $n$ components of the solution $x$ are chosen equally. Whenever $\mathcal{L} = e_{i}^{\top}$ ($l = 1$), the $i$th row of $I_{n}$ is chosen and only the $i$th part of the solution is chosen. Assume that $x_{\max }$ and $x_{\min }$ denote the highest and lowest elements of $x$ in absolute value, respectively. We select the $\mathcal{L}$ matrix for our condition numbers.

Here, $\rm{max}$ and $\rm{min}$ are the indices for $x_{\max }$ and $x_{\min }$, respectively. As a result, the components $x_{\max }$ and $x_{\min }$, the whole $x$, and the subvector $\left[x_{1} \, \ x_{2}\right]^{T}$, are chosen in accordance with the following four matrices.

In light of Table 1, the mixed and componentwise condition numbers may more directly convey the true conditioning of this TLSE problem than the normwise condition number. We also found that Algorithms A and B can yield accurate results from condition estimates based on SSCE.

The rest of this part is provided to evaluate the efficiency of the over-estimation ratios proposed in Algorithms A and C. Assume random perturbations

and fix

When the perturbations $\left\|\left[\begin{array}{c} \Delta \mathcal{Q} \\ \Delta \mathcal{A} \end{array}\right], \left[\begin{array}{cc} \Delta \mathbf{d}\\ \Delta \mathbf{b} \end{array} \right]\right\|_{F}$ are small enough, under the genericity condition (1.2), the following perturbed TLSE problem has the following unique solution, denoted by $x+\Delta x$:

where the perturbations $\Delta \mathcal{A}$ of $\mathcal{A}$, $\Delta \mathcal{Q}$ of $\mathcal{Q}$, $\Delta \mathbf{b}$ of $\mathbf{b}$, and $\Delta \mathbf{d}$ of $\mathbf{d}$ are represented by

In order to show the efficiency of unstructured over-estimation ratios of Algorithms A and B. We determine the following over-estimation ratios

To carry out the experiments, we generated 500 TLSE problems, where $\kappa_{\mathrm{SCE}}^{\mathrm{TLSE}, (\gamma)}$, $m_{\mathrm{SCE}}^{\mathrm{TLSE}, (\gamma)}$ and $c_{\mathrm{SCE}}^{\mathrm{TLSE}, (\gamma)}$ are the outcomes from Algorithms A and B. Generally, the ratios in $(0.1, 10)$ are acceptable [37,Chapter 19]. From Figure 1, we indicate that the mixed condition estimation $r_{m}$ and componentwise condition estimation $r_{c}$ are more effective than $r_{n}$ which may significantly overestimate the actual relative normwise error.

Regarding the structured TLSE problem, it is reasonable to take into consideration the fact that the perturbation $\Delta\mathcal{K}$ has the same structure as $\mathcal{K}$. For Toeplitz matrices, the assumption

for $\theta = m+n-1$ is satisfied, when

where the MATLAB-routine notation $\mathcal{K} =$ toeplitz $\left(T_{c}, T_{r}\right) \in S$ denotes a Toeplitz matrix with $T_{c} \in \mathbb{R}^{m}$ as its first column and $T_{r} \in \mathbb{R}^{n}$ as its first row; and, $\mathcal{K} = \sum_{i = 1}^{\theta} k_{i} S_{i}$, where $k = \left[T_{c}^{T}, T_{r}(2: \text { end })\right]^{T} \in \mathbb{R}^{m+n-1}$.

Example 5.2. A signal restoration implementation is the source of this example, which is derived from ^[25]. Assume that $\eta$ is 1.21 and $\nu$ is 4. The $\bar{\mathcal{K}}$ convolution matrix is a $m \times(m-2 \nu)$ Toeplitz matrix with the first column

and the rest is $k_{i 1} = 0$. Only $k_{11}$ is a non-zero value in this row. Now, we generate a Toeplitz matrix and a corresponding right-hand side vector in this manner.

Here, $G$ is a random Toeplitz matrix of the same structure as $\bar{\mathcal{K}}$, and $\bar{f}$ is the vector of all ones. A standard normal distribution is used to construct the $G$ and $h$ elements, and it scaled such that

We take $\omega = 0.001$ and $m = 300$ in our experiment. In this example we compare the structured normwise, mixed and componentwise condition numbers and interpret the effectiveness of Algorithm C.

Taking into account the data presented in Table 2, we are able to reach the conclusion that Algorithm C is capable of providing accurate estimates of the structured mixed and componentwise numbers, whereas the structured normwise condition estimation may significantly overestimate the true relative structured normwise condition number.

Example 5.3. In this example, we consider the data matrix $\mathcal{K}$ and the vector $f$ ^[3]

We note that the first $m-2$ singular values of $[\mathcal{K} \, f]$ are equal but larger than the $(m-1)$th singular $\sigma_{m-1}.$ It seems obvious that $\mathcal{K}$ is a Toeplitz matrix. Here we fix $\gamma = 2$ in all calculations for Algorithm C. For Toeplitz matrix $\mathcal{K}$ and the vector $f,$ we find that Algorithm C gives reliable componentwise condition estimations. From Table 3, we conclude that, in accordance with Theorem 4.7, the structured normwise mixed and componentwise condition numbers $\kappa_{n, s}$(k, f), $\kappa_{m, s}(k, f)$ and $\kappa_{c, s}(k, f)$, respectively, are consistently smaller than the corresponding unstructured ones $\kappa_{n}(K, f)$, $\kappa_{m}(K, f)$ and $\kappa_{c}(K, f)$ as a result of selecting different values of $m$ and $n$.

Example 5.4. Under structured perturbations, we can check the efficiency of structured condition estimations for the TLSE problem in the following example by taking 1000 samples of Toeplitz matrix $\mathcal{K}$ and $f$ as taken before in Example 5.3. We construct the componentwise structured perturbation matrix $\Delta \mathcal{K}$ and the perturbation vector $\Delta f$ for each sample as given below:

where $\varepsilon = 10^{-8}, \mathcal{E}$ is a Toeplitz matrix and $\mathcal{E}$ and $g$ are random matrices whose entries are uniformly distributed in the open interval $(-1, 1).$ Over estimation ratios with respect to the componentwise structured perturbations $\Delta \mathcal{K}$ and $\Delta f$ are given below:

Hence the structured condition estimations $m_{\mathrm{SCE}}^{\mathrm{STLSE}, (\gamma)}$ and $c_{\mathrm{SCE}}^{\mathrm{STLSE}, (\gamma)}$ are very reliable whereas the structured normwise condition estimation $\kappa_{\mathrm{SCE}}^{\mathrm{STLSE}, (\gamma)}$ may seriously overestimate the true relative normwise error for $\gamma = 2$ as shown in Figure 2.

6.   Conclusions

Using a dual technique, we have obtained explicit expressions for both the structured and unstructured condition numbers of the linear function of the TLSE problem in this article. Additionally, we investigated how the new results relate to the earlier findings. The comparisons between the structured and unstructured condition numbers are also given. We show that the previous structured condition numbers of the TLS problem can be recovered from the structured condition numbers of the TLSE problem. To efficiently estimate the structured and unstructured normwise, mixed, and componentwise conditions for the TLSE problem, we applied the SSCE method and constructed three algorithms. Finally, the performance of the proposed algorithms is illustrated in the numerical results. We have found that the structured condition numbers for the TLSE problem might be smaller than their unstructured counterparts, and that differences are significant. In the future, we will continue our research on this problem.

Acknowledgments

The authors are grateful to the handling editor and the anonymous referees for their constructive feedback and helpful suggestions. This work was supported by the Zhejiang Normal University Postdoctoral Research Fund (Grant No. ZC304022938), the Natural Science Foundation of China (Project No. 61976196) and the Zhejiang Provincial Natural Science Foundation of China under Grant No. LZ22F030003.

Conflict of interest

The authors declare no conflict of interest.