Norm-Constrained Least-Squares Solutions to the Matrix Equation AXB = C

Theorem 1. Matrix X^* is a solution of the problem (3) if and only if there is a scalar λ^* ≥ 0 such that the following conditions are satisfied:

Proof. Assume that there is a scalar λ^* ≥ 0 such that the conditions (4) are satisfied. Let

For any matrix W ∈ R^m×n, we have This implies that X^* is a global minimizer of the function $$. Since $$ for all X ∈ R^m×n, we have The equality λ^*(∥X^*∥ − Δ) = 0 implies that λ^*(〈X^*, X^*〉 − Δ²) = 0. Consequently, the following inequality always holds: Hence, from λ^* ≥ 0, we have φ(X) ≥ φ(X^*) for all X ∈ R^m×n with ∥X∥ ≤ Δ. And so X^* is a global minimizer of (3).

Conversely, assuming that X^* is a global solution of the problem (3), we show that there is a nonnegative λ^* such that satisfies conditions (4). For this purpose we consider two cases: ∥X^*∥ < Δ and ∥X^*∥ = Δ.

In case ∥X^*∥ < Δ, X^* is certainly an unconstrained minimizer of φ(X). So X^* satisfies the stationary point condition ∇φ(X^*) = 0; that is, A^TAX^*BB^T − A^TCB^T = 0. This implies that the properties (4) hold for λ^* = 0. In the case ∥X^*∥ = Δ, the second equality is immediately satisfied, and X^* also solves the constrained problem

By applying optimality conditions for constrained optimization to this problem, we know that there exists a scalar λ^* such that the Lagrangian function defined by has a stationary point at X^*. By setting ∇_Xζ(X^*, λ^*) to zero, we obtain Now the proof is concluded by showing that λ^* ≥ 0. Since the equality (11) holds, then X^* minimizes $$, and so we have for all X ∈ R^m×n. Suppose that there are only negative values of λ^* that satisfy (11). Then we have from (12) that Since we already know that X^* minimizes φ(X) for ∥X∥ ≤ Δ, it follows that X^* is in fact a global, unconstrained minimize of φ(X). Therefore conditions (11) hold when λ^* = 0, which contradicts our assumption that only negative values of λ^* can satisfy condition (11). The proof is completed.

Algorithm 2. (i) Given matrices X₀ = 0, Q₋₁ = 0 and a small tolerance ε > 0. Compute

•  

  R₀ = −A^TCB^T,  t₀ = −A^TCB^T,  γ₀ = ∥R₀∥,  P₀ = −R₀,  T₋₁ = [].

•  

  Set k ← 0.

(ii) Computing Q_k = t_k/γ_k, $$, t_k+1 = A^TAQ_kBB^T − δ_kQ_k − γ_kQ_k−1, γ_k+1 = ∥t_k+1∥

•  

  $$, where Γ_k = (0, …, 0, γ_k) ^T ∈ R^k.

(iii) If AP_kB ≠ 0, compute $$.

•  

  If ∥X_k + α_kP_k∥ ≤ Δ, computing R_k+1 = R_k + α_kA^TAP_kBB^T, $$, X_k+1 = X_k + α_kP_k, P_k+1 = −R_k+1 + β_kP_k, else, go to Step 4.

•  

  If ∥R_k+1∥ < ε, stop, else set k ← k + 1 and go to Step 2.

(iv) Find the solution h_k to the following optimization problem:

(v) If γ_k+1|〈e_k+1, h_k〉| < ε (here e_k+1 represents the last column of identity matrix I), set

$$ and then stop, else set k ← k + 1 and go to Step 2.

Theorem 3. Assume that the sequences {R_i}, {P_i}, and {AP_iB} are generated by Algorithm 2; then the following equalities hold for all i ≠ j, 0 ≤ i,  j ≤ k:

Proof. Since 〈A, B〉 = 〈B, A〉 holds for all matrices A and B, we only need to prove that the conclusion holds for all 0 ≤ i < j ≤ k. Using induction and two steps are required.

Step 1. Show that 〈R_i, R_i+1〉 = 0, 〈P_i, R_i+1〉 = 0 and 〈AP_iB, AP_i+1B〉 = 0 hold for all i = 0,1, 2, …k. We also use the principle of mathematical induction to prove these conclusions. When i = 0, we have

Assume that conclusion holds for all i ≤ s  (0 < s < k); then By the principle of induction, 〈P_i, R_i+1〉 = 0, 〈R_i, R_i+1〉 = 0, and 〈AP_iB, AP_i+1B〉 = 0 hold for all i = 0,1, 2, …k.

Step 2. Assume that 〈P_i, R_i+l〉 = 0, 〈AP_iB, AP_i+lB〉 = 0, and 〈R_i, R_i+l〉 = 0 for all 0 ≤ i ≤ k and 1 < l < k, show that 〈P_i, R_i+l+1〉 = 0, 〈AP_iB, AP_i+l+1B〉 = 0, and 〈R_i, R_i+l+1〉 = 0. The proof is as follows:

From Steps 1 and 2, we have by principle induction that 〈R_i, R_j〉 = 0, 〈P_i, R_j〉 = 0, 〈AP_iB, AP_jB〉 = 0 hold for 0 ≤ i < j ≤ k.

Theorem 4. Assume that the sequence {Q_i} is generated by Algorithm 2; then the following equalities hold:

Proof. By the definition of Q_i, we immediately know that 〈Q_i, Q_i〉 = 1  (i = 0,1, 2, …). Similar to the proof of Theorem 3, we also use the principle of mathematical induction to prove this conclusion with the two following cases.

Step 1. Show that 〈Q_i, Q_i+1〉 = 0 for all i = 0,1, 2, …k.

When i = 0, we have

Assume that conclusion holds for all i ≤ s  (0 < s < k); then By the principle of induction, 〈Q_i, Q_i+1〉 = 0 holds for all i = 0,1, 2, …k.

Step 2. Assume that 〈Q_i, Q_i+l〉 = 0 for all 0 ≤ i ≤ k and 1 < l < k show that 〈Q_i, Q_i+l+1〉 = 0. The proof is as follows:

From steps 1 and 2, we have by the principle of mathematical induction that 〈Q_i, Q_j〉 = 0 hold for all i, j = 0,1, 2, …k,   i ≠ j.

Theorem 5. Assume that the sequences {γ_k}, {T_k}, and {Q_i} are generated by Algorithm 2. Let

Then the following equality holds: where e₁ represents the first column of identity matrix I.

Proof. By the definition of T_k and Q_k  (k = 0,1, 2, …), we have

Hence, we have So the equality (24) holds. In addition, from above equality, we have$$ for all  h ∈ R^k+1. So  T_k  is positive semi-definite. The proof is completed.

Theorem 6. Assume that the sequences {Q_k}, {R_k}, {γ_k}, {δ_k}, {α_k}, and {β_i} are generated by Algorithm 2, then the following equalities hold for all k = 0,1, 2, …:

Proof. (the proof of the first equality in (27)). By the definition of Q_k and R_k, we have

where a_i, b_i  (i = 0,1, 2, …, k) are positive numbers. These equalities imply that Q_k and R_k belong to the same space And furthermore we can have By Theorems 3 and 4, we have Q_k⊥K_k−1 and R_k⊥K_k−1. Hence Q_k and R_k must be linear correlation, so there exists a real number c_k such that Q_k = c_kR_k. Noting that ∥Q_k∥ = 1, we have by (28) that Q_k = (−1) ^kR_k/∥R_k∥.

(The proof of the second equality in (27)). Noting that the first equality in (27) holds, then, when k = 0, we have

When k > 0, we have (The proof of the third equality in (27)). By the definition of γ_k, we have Hence the third equality in (27) holds. The proof is completed.

Remark 7. This theorem shows the relationship between the sequences  {Q_k}, {R_k}, {γ_k}, {δ_k}, {α_k}, and {β_i} to lower down the cost of calculation.

Theorem 8. Assume that the sequences {X_k}, {R_k} are generated by Algorithm 2. Then the following equalities hold for all k = 0,1, 2, …:

Proof. We use the principle of mathematical induction to prove this conclusion. When k = 0, obviously, the conclusion holds. Assume that the conclusion holds for k − 1; then

This implies that the conclusion holds for k. By the principle of mathematical induction, we know that the conclusion holds for all k = 0,1, 2, ….

Remark 9. For Theorem 3, the sequences R₀, R₁, R₂, … are orthogonal to each other in the finite dimension matrix space R^n×n; it is certain that there exists a positive number k + 1 ≤ n² such that R_k+1 = 0. So without the error of calculation, the first stopping criterion in the algorithm will perform with finite steps. From Theorem 8, we get A^TAX_k+1BB^T − A^TCB^T = 0. According to Theorem 1, when we set λ^* = 0, X_k+1 is a solution of the problem (3).

Theorem 10. Assume that the sequences {Q_k}, {γ_k}, and {h_k} are generated by Algorithm 2. Let

Then, for all k = 0,1, 2, …, there exists a nonnegative number λ_k such that

Proof. Assume that h_k is the solution of optimization problem (14); then there exists a nonnegative number λ_k such that the following optimality Karush-Kuhn-Tucker (KKT) conditions are satisfied:

Noting that $$ and the second equality in (38) hold, we know that the second equality in (37) holds.

Since the first equality in (38) can be rewritten as

so we have Hence, we have The proof is completed.

Theorem 11. Assume that γ₀, γ₁, …, γ_k ≠ 0, and γ_k+1 = 0. Then $$ is the solution of the problem (1).

Proof. Since γ_k+1 = 0 and $$, we have by Theorem 10 that

which implies that $$ is the solution of the problem (1).

Remark 12. According to Theorem 4, the sequences Q₀, Q₁, Q₂, … are orthogonal each other in the finite dimension matrix space R^n×n; it is certain that there exists a positive number k ≤ n² such that Q_k = 0. Since t_k = γ_kQ_k = 0, then $$. So without the error of calculation, the second stopping criterion in the algorithm also performs with finite steps.

Remark 13. According to Remarks 9 and 12, we have that, without the error of calculation, a desired solution can be obtained with finitely iterative step by Algorithm 2.

Theorem 14. The solution h_k of the problem (14) obtained by Algorithm 2 is on the boundary. In other words, h_k is the solution of the following optimization problem:

Proof. Assuming that the solution h_k of the problem (14) obtained by Algorithm 2 is inside the boundary, we have by (38) that T_kh_k = −γ₀e₁. By Theorem 5, we know T_k is a positive semidefinite matrix. If T_k is positive definite, then $$ with ∥h_k∥ < Δ is a unique solution of the problem (14). Hence, we have by Theorem 5 that X = (Q₀, Q₁, …, Q_k)(h_k ⊗ I) with ∥X∥ = ∥h_k∥ < Δ is a unique solution of the problem (1). In this case, the step of solving the problem (14) in Algorithm 2 cannot be implemented. If T_k is positive semidefinite and not positive definite, then there exists a matrix Z such that T_k(h_k + Z) = −γ₀e₁ and ∥h_k + Z∥ = Δ which implies that h_k + Z is a solution to the problem (1) on the boundary. This contradicts our assumption.

Algorithm 15. (I) Let a suitable starting value $$ and Δ > 0 be given.

(II) For i = 0,1, … until convergence.

• (a)

  Factorize $$, where Q and Λ are unit bidiagonal and diagonal matrix, respectively.

• (b)

  Solve QΛQ^Th = −γ₀e₁.

• (c)

  Solve Qw = h.

• (d)

  Set $$.

In the implementation of Algorithm 15, the initial secular $$ can be chosen by the following principles: If ∥h_k(λ_k−1)∥ ≥ Δ, let $$; else let $$, where λ_k−1 is obtained by the (k − 1)th iterative steps of Algorithm 2. The stopping criteria can be used as $$, where ε is a small tolerance.

Algorithm 16. (i) Given matrices X₀ = 0, Q₋₁ = 0 and a small tolerance ε > 0.

Computing R₀ = −A^TCB^T,  t₀ = −A^TCB^T.

Set γ₀ = ∥R₀∥,  P₀ = −R₀,  T₋₁ = [], and k ← 0.

(ii) If AP_kB ≠ 0, compute

where Γ_k = (0, …, 0, γ_k) ^T ∈ R^k.

Else, computing Q_k = t_k/γ_k (the first one Q_k = (−1) ^kR_k/∥R_k∥),

(iii) If ∥X_k+1 + α_k+1P_k+1∥ ≤ Δ, computing X_k+1 = X_k + α_kP_k, P_k+1 = −R_k + β_kP_k.

If ∥R_k+1∥ ≤ ε, stop. Else, setting k ← k + 1 and go to Step 2.

Else, go to Step 4.

(iv) Using Algorithm 15 to compute the solution h_k of the problem (43).

(v) If γ_k+1|〈e_k+1, h_k〉| < ε, setting $$, then stop.

Else, setting k ← k + 1 and go to step 2.

Example 17. Given the matrices A,  B,  C as follows:

Example 18. We work with a 2D first-kind Fredholm integral equation of the generic form

where κ and ω are function. Based on [12], we have that the discretization of the problem (51) leads to the linear relation $$ between the discrete solution F and the discrete data G, where

An example of such problem is image denoising with a Gaussian point spread function:

which is used as a model for out-of-focus as well as atmospheric turbulence blur [13]. In Figure 1(a), the original image is the standard test image of Lena with size 256   ×   256, which is also a 256   ×   256 matrix F^′. After the image was blurred by Gaussian kernel (53) with σ = 0.01, we get Figure 1(b); that is the matrix $$. In image denoising, our target is to get the solution of $$. Tikhonov regularization is needed to treat this problem in order to control the effect of the noise on the solution. As we have said in Section 1, Tikhonov regularization is equivalent to over the norm inequality constraint matrix equation