Kaczmarz algorithm in Hilbert space Ryszard Szwarc joint work with Rainis Haller

This work was inspired by the paper by S. Kwapień and J. Mycielski (Studia Mathematica 148 (2001), 75–86).

Let {e_{n}}_{n=0}^{∞} ⊂ H, ∥e_{n}∥ = 1. For given x we get numbers {(x, e_{n})}_{n=0}^{∞}. We want to reconstruct x in terms of these numbers. The sequence {e_{n}}_{n=0}^{∞} should be linearly dense. Define

x_{0} = (x, e_{0})e_{0},
x_{n} = x_{n−1} + (x − x_{n−1}, e_{n})e_{n}.

The formula is called the Kaczmarz algorithm. We are interested when x_{n} → x for any x ∈ H. Sequences {e_{n}}_{n=0}^{∞} for which this holds will be called effective.

When {e_{n}}_{n=0}^{∞} is orthonormal the algorithm returns the partial sums

x_{n} = ∑_{i=0}^{n}(x, e_{i})e_{i}.

Kaczmarz (1937) proved that if dim H < +∞ and {e_{n}}_{n=0}^{∞} is periodic and spans H, then {e_{n}}_{n=0}^{∞} is effective.

Let P_{n} be the orthogonal projection onto e_{n}^{⊥}. Then

x_{n} = x_{n−1} + (I − P_{n})(x − x_{n−1})
x − x_{n} = P_{n}(x − x_{n−1})
x − x_{n} = P_{n}P_{n−1} … P_{1}P_{0}x.

The sequence is effective iff P_{n}P_{n−1} … P_{1}P_{0} tends to zero strongly.

Let dim H < ∞ and {e_{n}}_{n=0}^{∞} be N-periodic. For A = P_{N−1} … P_{1}P_{0} it suffices to show that A^{n} tends to zero. We claim that ∥A∥ < 1. If not there is a vector x such that ∥Ax∥ = ∥x∥ = 1. Then ∥P_{0}x∥ ≥ ∥Ax∥ = ∥x∥, hence P_{0}x = x. Similarly P_{1}x = x, …, P_{N−1}x = x, which implies that x ⊥ e_{0}, e_{1}, …, e_{N−1}. Thus x = 0.

Assume (temporarily) linear independence of vectors {e_{n}}_{n=0}^{∞}. We have x_{n} ∈ span {e_{0}, …, e_{n}}.

x_{n} = ∑_{i=0}^{n}(x, g_{i})e_{i},  (1)

where g_{i} ∈ H. It can be verified by induction that

g_{n} = e_{n} − ∑_{i=0}^{n−1}(e_{n}, e_{i})g_{i}.  (2)

We can define g_{n} by (2) and then check that (1) holds. In this way we remove the linear independence assumption. The formula (2) can be written as

e_{n} = ∑_{i=0}^{n} m_{ni}g_{i}, m_{ni} = (e_{n}, e_{i}).

By (2) there are numbers c_{nj} such that

g_{n} = ∑_{j=0}^{n} c_{nj}e_{j}, c_{nn} = 1.  (3)

The coefficients {c_{nj}}_{n>j} are crucial. We obtain these numbers by taking the inverse to the matrix I + M where

M = (\begin{matrix}0 & 0 & 0 & 0 & 0 & … \\ m_{10} & 0 & 0 & 0 & 0 & … \\ m_{20} & m_{21} & 0 & 0 & 0 & … \\ m_{30} & m_{31} & m_{32} & 0 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ... \end{matrix})

U = (\begin{matrix}0 & 0 & 0 & 0 & 0 & … \\ c_{10} & 0 & 0 & 0 & 0 & … \\ c_{20} & c_{21} & 0 & 0 & 0 & … \\ c_{30} & c_{31} & c_{32} & 0 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ... \end{matrix})

(I + U)(I + M) = (I + M)(I + U) = I.
UM = MU = −U − M.

Proposition 1. Let U and M be strictly lower triangular matrices such that MU = UM = −U − M. Then

∥U∥ ≤ 1 iff M + M^{∗} + I ≥ 0.

In that case there is a Hilbert space H and vectors {e_{n}}_{n=0}^{∞} such that M + M^{∗} + I is the Gram matrix of these vectors.

Proof. Let

M_{n} = (\begin{matrix}0 \\ m_{10} & 0 \\ ⋮ & ... & 0 \\ m_{n0} & ⋯ & m_{n,n−1} & 0 \\ 0 & ⋯ & 0 & ... \\ ⋮ & ⋮ & ⋮ & ⋮ \end{matrix}) U_{n} = (\begin{matrix}0 \\ c_{10} & 0 \\ ⋮ & ... & 0 \\ c_{n0} & ⋯ & c_{n,n−1} & 0 \\ 0 & ⋯ & 0 & ... \\ ⋮ & ⋮ & ⋮ & ⋮ \end{matrix})

Then (I + M_{n})(I + U_{n}) = (I + U_{n})(I + M_{n}) = I. Assume M + M^{∗} + I ≥ 0. Hence M_{n} + M_{n}^{∗} + I ≥ 0 and 0 ≤ (U_{n}^{∗} + I)(M_{n} + M_{n}^{∗} + I)(U_{n} + I) = I − U_{n}^{∗}U_{n} Hence ∥U_{n}∥ ≤ 1 and ∥U∥ ≤ 1.

The converse implication follows from

(M_{n}^{∗} + I)(I − U_{n}^{∗}U_{n})(M_{n} + I) = M_{n} + M_{n}^{∗} + I.

♢

By construction of the algorithm we have

x − x_{n} ⊥ e_{n}

because x − x_{n} = P_{n}(x − x_{n−1}). From x_{n} = ∑_{i=0}^{n}(x, g_{i})e_{i} we obtain

x − x_{n−1} = x − x_{n} + (x, g_{n})e_{n}.
∥x − x_{n−1}∥^{2} = ∥x − x_{n}∥^{2} + |(x, g_{n})|^{2}, n ≥ 1,
∥x∥^{2} = ∥x − x_{0}∥^{2} + |(x, g_{0})|^{2}.

Hence

∥x∥^{2} − lim_{n} ∥x − x_{n}∥^{2} = ∑_{n=0}^{∞} |(x, g_{n})|^{2}.

Therefore effectiveness is equivalent to

∥x∥^{2} = ∑_{n=0}^{∞} |(x, g_{n})|^{2}

for any x ∈ H. Our main result is Theorem 1. The sequence {e_{n}}_{n=0}^{∞} is effective if and only if it is linearly dense and U is a partial isometry, i.e. U^{∗}U is a projection.

These two results can be interpreted as follows. We have as many effective sequences among sequences of unit vectors as partial isometries among strictly lower triangular contractions.

Kwapień and Mycielski showed that if we choose the sequence of unit vectors at random then almost surely we end up with an effective sequence. More precisely fix a Borel measure μ on the unit sphere of H, such that the support of μ is linearly dense. Then draw consecutive vectors independently with respect to that measure.

Proof of Theorem 1. Assume effectiveness. Hence

(x, y) = ∑_{n=0}^{∞}(x, g_{n})(g_{n}, y).

In particular

m_{ij} = (e_{i}, e_{j}) = ∑_{n=0}^{∞}(e_{i}, g_{n})(g_{n}, e_{j}).

Lemma 1.

(g_{n}, e_{j}) = ((UM^{∗} + M^{∗} + I)δ_{j}, δ_{n})_{ℓ^{2}(ℕ)}

♢

Let A = UM^{∗} + M^{∗} + I. We have

m_{ij} = ∑_{n=0}^{∞}(Aδ_{j}, δ_{n})_{ℓ^{2}}(δ_{n}, Aδ_{i})_{ℓ^{2}} = (Aδ_{j}, Aδ_{i})_{ℓ^{2}}.

Assume for simplicity that A is bounded on ℓ^{2}. Therefore we have

M + M^{∗} + I = A^{∗}A.

Taking into account relation between U and M gives

A^{∗}A = MU^{∗}UM^{∗} − MM^{∗} + M + M^{∗} + I.

Hence

MM^{∗} = MU^{∗}UM^{∗}

or

(M^{∗}δ_{j}, M^{∗}δ_{i})_{ℓ^{2}} = (UM^{∗}δ_{j}, UM^{∗}δ_{i})_{ℓ^{2}}.  (4)

The last formula makes sense when M is unbounded, because M^{∗} leaves the space F(ℕ) = span {δ_{0}, δ_{1}, …} invariant. This formula can be proved directly by replacing A with A_{n} = U_{n}M_{n}^{∗}+ M_{n} + I and taking the limit. (4) states that U is an isometry on

H_{0} = \overline{M^{∗}(F(ℕ))}.

The proof will be completed if we show that U vanishes on H_{0}^{⊥}. We have

U^{∗}, M^{∗} : F(ℕ) → F(ℕ)

hence

M^{∗}(U^{∗} + I) = −M^{∗} − U^{∗} + M^{∗} = −U^{∗}.

Therefore U^{∗}(F(ℕ)) ⊂ M^{∗}(F(ℕ)) ⊂ H_{0} and consequently

H_{0}^{⊥} ⊂ ker U.

Conversely, let U be a partial isometry. Hence U is isometric on H_{0} = \overline{U^{∗}(F(ℕ))}. The formula

U^{∗}(M^{∗} + I) = −M^{∗}

yields that

U^{∗}(F(ℕ)) ⊃ M^{∗}(F(ℕ)).

Hence U is an isometry on M^{∗}(F(ℕ)). This implies the formula

(M^{∗}δ_{j}, M^{∗}δ_{i})_{ℓ^{2}} = (UM^{∗}δ_{j}, UM^{∗}δ_{i})_{ℓ^{2}}.

Now we can track backwards the proof of the first part to obtain the conclusion. ♢

Particular case

Assume \overline{M^{∗}(F(ℕ))} = ℓ^{2}(ℕ). Recall that \overline{M^{∗}(F(ℕ))} is a carrier space of U. This case is equivalent to U^{∗}U = I and occurs when the rows of the matrix M span a dense subspace of ℓ^{2}(ℕ). For example this is the case when m_{n,n−1} ≠ 0 for any n.

(\begin{matrix}0 \\ m_{10} & 0 \\ ∗ & m_{21} & 0 \\ ∗ & ∗ & m_{32} & 0 \\ ⋮ & ⋮ & & ... & ... \end{matrix})

We say that the sequence {e_{n}}_{n=0}^{∞} is strongly effective if {e_{n}}_{n=k}^{∞} is effective for each k. This is highly nonorthogonal case.

Theorem 2. Assume {e_{n}}_{n=0}^{∞} is linearly dense. Then {e_{n}}_{n=0}^{∞} is strongly effective if and only if U^{∗}U = I.

Proof. Let U^{∗}U = I and let M^{(k)} and U^{(k)} denote truncated matrices when we remove the first k rows and the first k columns.

These matrices correspond to the sequence {e_{n}}_{n=k}^{∞}. Also since U is lower triangular we get

(U^{(k)})^{∗}U^{(k)} = I,

hence U^{(k)} is a partial isometry. It suffices to show that {e_{n}}_{n=k}^{∞} is linearly dense. It can be shown that U^{∗}U = I implies

e_{j} = − ∑_{i=j+1}^{∞} \overline{c_{ij}}e_{i}

which means that removing finitely many vectors doesn’t spoil linear density of the system. In view of Theorem 1 the sequence {e_{n}}_{n=k}^{∞}is effective.

Conversely let {e_{n}}_{n=0}^{∞} be strongly effective. Let Q_{k} denote the orthogonal projection onto the orthogonal complement of {δ_{0}, δ_{1} …, δ_{k−1}}. Let U_{(k)} = UP_{k}. Then U_{(k)} = 0_{k} ⊕ U^{(k)}. Hence U_{(k)} are partial isometries as well as U. But this is possible only if U^{∗}U and P_{k} commute (Exercise). On the other hand if U^{∗}U commutes with P_{k} for any k then U^{∗}U must be diagonal. Assume that U^{∗}U ≠ I. Then Uδ_{j} = 0 for some j. This implies that e_{j} is orthogonal to all the vectors e_{i}, i ≠ j. Hence {e_{n}}_{n=0}^{∞} cannot be strongly effective. ♢ Theorem 3. Assume {e_{n}}_{n=0}^{∞} is strongly effective. Then

∑_{i=0}^{∞} |(e_{i}, e_{j})|^{2} = +∞

for any j. Lemma 2. U^{∗}U = I implies U^{∗}M = −M − I.

Proof. (incorrect) Assume M is bounded. Then M = (U^{∗}U)M = U^{∗}(UM) = U^{∗}(−U − M) = −I − U^{∗}M.

♢

From Lemma 2 we have U^{∗}(M + M^{∗} + I)

= −M − I − M^{∗} − U^{∗} + U^{∗} = −(M + M^{∗} + I).

Let G = M + M^{∗} + I. We have U^{∗}G = −G. Assume that

∑_{i=0}^{∞} |(e_{i}, e_{j})|^{2} < +∞

for some j. Then x := Gδ_{j} ∈ ℓ^{2}. Consequently U^{∗}x = −x and

(U^{∗})^{n}x = (−1)^{n}x.

But ∥U^{∗}∥ ≤ 1 and U^{∗} is strictly upper triangular. Hence (U^{∗})^{n} tends to zero strongly which implies x = 0. This is a contradiction, because x_{j} = (e_{j}, e_{j}) = 1. ♢

Stationary case

Assume

(e_{i+1}, e_{j+1}) = (e_{i}, e_{j})

Then the matrix M is constant on diagonals.

M = (\begin{matrix}0 \\ a_{1} & 0 \\ a_{2} & a_{1} & 0 \\ a_{3} & a_{2} & a_{1} & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix})

By the Herglotz theorem there is a measure μ on the unit circle such that

(e_{i+n}, e_{i}) = a_{n} = ∫_{𝕋} z^{n}dμ(z).

Kwapień and Mycielski showed that a stationary linearly dense sequence {e_{n}}_{n=0}^{∞} is effective if and only if either μ is the Lebesgue measure (orthogonal case) or it is singular with respect to the Lebesgue measure. Also U is constant on diagonals, i.e. it is a Toeplitz operator.

U = (\begin{matrix}0 \\ u_{1} & 0 \\ u_{2} & u_{1} & 0 \\ u_{3} & u_{2} & u_{1} & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix})

U is unitarily equivalent to multiplication operator on H^{2}(𝕋) with the function

u(z) = ∑_{n=1}^{∞} u_{n}z^{n}.

Moreover

∥U∥ = ∥u(z)∥_{H^{∞}(𝕋)} ≤ 1.

Now multiplication with u(z) is a partial isometry if and only if the boundary values of |(u(z)| are equal 0 or 1. By F. Riesz and M. Riesz Theorem u(z) ≡ 0 or |u(z)| ≡ 1. The first case corresponds to orthogonal systems, because M = 0. The second case was the key point in the paper by Kwapień and Mycielski in proving that μ is singular.

Open problem

Fix h ∈ L^{2}(𝕋) such that ĥ(n) ≠ 0 for any n. Then the translates of h_{t}, where h_{t}(z) = h(tz) span a dense subspace. Fix a sequence of numbers t_{n} ∈ 𝕋. Kwapień and Mycielski showed that if t_{n} = t^{n}, where t is not a root of identity, then the sequence h_{t_{n}} is effective, because this sequence is stationary and its spectral measure is discrete. Also they showed that if t_{n} are independent random variables with uniform distribution on 𝕋 then almost surely the sequence h_{t_{n}} is effective.

The problem is: for given h determine the sequences of unit numbers t_{n} leading to effectiveness of the sequence h_{t_{n}}.

Open problem by Mycielski

Let {e_{n}}_{n=0} be linearly dense. By using the proof of Kaczmarz theorem it can be shown that there exists a function σ : ℕ → ℕ such that the sequence {e_{σ(n)}}_{n=0}^{∞} is effective. The consecutive values of such function may look as follows

0, 1, …, 0, 1, 0, 1, 2, …, 0, 1, 2, 0, 1, 2, 3, …, 0, 1, 2, 3, …

The number of repetition of the block 0, 1, 2, …, k is set in such a way that the norm of the operator P_{k}P_{k−1} …, P_{0} restricted to the space spanned by e_{0}, e_{1}, …, e_{k} is less than 1/k.

The question is if there exists a function σ which is ”good” for any linearly dense sequence {e_{n}}_{n=0}^{∞}, i.e. the sequence {e_{σ(n)}}_{n=0}^{∞} is always effective.