We prove that any tight frame {gn}(n=0),(infinity) with parallel to go parallel to = 1, in a Hilbert space can be obtained by the kaczmarz algorithm. The uniqueness of the correspondence is determined. (c) 2006 Elsevi...
详细信息
We prove that any tight frame {gn}(n=0),(infinity) with parallel to go parallel to = 1, in a Hilbert space can be obtained by the kaczmarz algorithm. The uniqueness of the correspondence is determined. (c) 2006 Elsevier Inc. All rights reserved.
The kaczmarz method is an iterative method for solving large systems of equations that projects iterates orthogonally onto the solution space of each equation. In contrast to direct methods such as Gaussian eliminatio...
详细信息
ISBN:
(纸本)9781479929719
The kaczmarz method is an iterative method for solving large systems of equations that projects iterates orthogonally onto the solution space of each equation. In contrast to direct methods such as Gaussian elimination or QR-factorization, this algorithm is efficient for problems with sparse matrices, as they appear in constraint-based user interface (UI) layout specifications. However, the kaczmarz method as described in the literature has its limitations: it considers only equality constraints and does not support soft constraints, which makes it inapplicable to the UI layout problem. In this paper we extend the kaczmarz method for solving specifications containing soft constraints, using the prioritized IIS detection algorithm. Furthermore, the performance and convergence of the proposed algorithms are evaluated empirically using randomly generated UI layout specifications of various sizes. The results show that these methods offer improvements in performance over standard methods like Matlab's LINPROG, a well-known efficient linear programming solver.
The kaczmarz algorithm is an iterative method for solving a system of linear equations. It can be extended so as to reconstruct a vector x in a (separable) Hilbert space from the inner-products {< x,phi n & ran...
详细信息
The kaczmarz algorithm is an iterative method for solving a system of linear equations. It can be extended so as to reconstruct a vector x in a (separable) Hilbert space from the inner-products {< x,phi n & rang;}. The kaczmarz algorithm defines a sequence of approximations from the sequence {< x,phi n & rang;};these approximations only converge to x when {phi n} is effective. We dualize the kaczmarz algorithm so that x can be obtained from {< x,phi n & rang;} by using a second sequence {psi n}in the reconstruction. This allows for the recovery of x even when the sequence {phi n} is not effective;in particular, our dualization yields a reconstruction when the sequence {phi n} is almost effective. We also obtain some partial results characterizing when the sequence of approximations from {< x,phi n & rang;} using {psi n} converges to x, in which case {(phi n,psi n)} is called an effective pair.
The distributed kaczmarz algorithm is an adaptation of the standard kaczmarz algorithm to the situation in which data is distributed throughout a network represented by a tree. We isolate substructures of the network ...
详细信息
The distributed kaczmarz algorithm is an adaptation of the standard kaczmarz algorithm to the situation in which data is distributed throughout a network represented by a tree. We isolate substructures of the network and study convergence of the distributed kaczmarz algorithm for relatively large relaxation parameters associated to these substructures. If the system is consistent, then the algorithm converges to the solution of minimal norm;however, if the system is inconsistent, then the algorithm converges to an approximated least-squares solution that is dependent on the parameters and the network topology. We show that the relaxation parameters may be larger than the standard upper-bound in literature in this context and provide numerical experiments to support our results. (C) 2020 Elsevier Inc. All rights reserved.
We propose a new greedy kaczmarz algorithm for the solution of very large systems of linear equations. In our proposed algorithm, control sequence is determined by a greedy rule, and relaxation parameters are determin...
详细信息
We propose a new greedy kaczmarz algorithm for the solution of very large systems of linear equations. In our proposed algorithm, control sequence is determined by a greedy rule, and relaxation parameters are determined adaptively. Convergence of our proposed algorithm is proved. Numerical results show that the proposed algorithm is feasible and has faster convergence rate than the greedy randomized kaczmarz algorithm. (C) 2019 Elsevier Ltd. All rights reserved.
We propose a new deterministic kaczmarz algorithm for solving consistent linear systems Ax = b. Basically, the algorithm replaces orthogonal projections with reflections in the original scheme of Stefan kaczmarz. Buil...
详细信息
We propose a new deterministic kaczmarz algorithm for solving consistent linear systems Ax = b. Basically, the algorithm replaces orthogonal projections with reflections in the original scheme of Stefan kaczmarz. Building on this, we give a geometric description of solutions of linear systems. Suppose A is m \times n, we show that the algorithm generates a series of points distributed with patterns on an (n -1)-sphere centered on a solution. These points lie evenly on 2m lower-dimensional spheres {Sk0, Sk1}km=1, with the property that for any k, the midpoint of the centers of Sk0, Sk1 is exactly a solution of Ax = b. With this discovery, we prove that taking the average of O(eta (A) log(1/\varepsilon )) points on any Sk0 \cupSk 1 effectively approximates a solution up to relative error \varepsilon , where eta(A) characterizes the eigengap of the orthogonal matrix produced by the product of m reflections generated by the rows of A. We also analyze the connection between eta(A) and \kappa (A), the condition number of A. In the worst case eta(A) = O(\kappa2(A) log m), while for random matrices eta(A) = O(\kappa (A)) on average. Finally, we prove that the algorithm indeed solves the linear system ATW -1Ax = ATW-1b, where W is the lower-triangular matrix such that W + WT = 2AAT. The connection between this linear system and the original one is studied. The numerical tests indicate that this new kaczmarz algorithm has comparable performance to randomized (block) kaczmarz algorithms.
The kaczmarz algorithm (KA) is a popular method for solving a system of linear equations. In this note we derive a new exponential convergence result for the KA. The key allowing us to establish the new result is to r...
详细信息
The kaczmarz algorithm (KA) is a popular method for solving a system of linear equations. In this note we derive a new exponential convergence result for the KA. The key allowing us to establish the new result is to rewrite the KA in such a way that its solution path can be interpreted as the output from a particular dynamical system. The asymptotic stability results of the corresponding dynamical system can then be leveraged to prove exponential convergence of the KA. The new bound is also compared to existing bounds.
The kaczmarz algorithm is widely used in image reconstruction. In this paper, we propose an enhanced version of the kaczmarz algorithm by integrating Nesterov momentum into the kaczmarz algorithm, denoted as the Kaczm...
详细信息
The kaczmarz algorithm is widely used in image reconstruction. In this paper, we propose an enhanced version of the kaczmarz algorithm by integrating Nesterov momentum into the kaczmarz algorithm, denoted as the kaczmarz algorithm with momentum. Our innovation offers a novel approach to accelerate the convergence rate of the kaczmarz algorithm significantly. Based on greedy rules for selecting work row, we prove that the kaczmarz method with momentum can achieve global linear convergence rates. Furthermore, we extend a constrained version of the kaczmarz algorithm with Nesterov momentum for improved image reconstruction and prove its convergence. Numerical experiments show that the proposed algorithm outperforms the original kaczmarz algorithm in terms of efficiency for image reconstruction.
The kaczmarz algorithm is a common iterative method for solving linear *** an effective variant of kaczmarz algorithm,the greedy kaczmarz algorithm utilizes the greedy selection *** two-subspace projection method perf...
详细信息
The kaczmarz algorithm is a common iterative method for solving linear *** an effective variant of kaczmarz algorithm,the greedy kaczmarz algorithm utilizes the greedy selection *** two-subspace projection method performs an optimal intermediate projection in each *** this paper,we introduce a new greedy kaczmarz method,which give full play to the advantages of the two improved kaczmarz algorithms,so that the generated iterative sequence can exponentially converge to the optimal *** theoretical analysis reveals that our algorithm has a smaller convergence factor than the greedy kaczmarz *** results confirm that our new algorithm is more effective than the greedy kaczmarz method for coherent systems and the two-subspace projection method for appropriate scale systems.
In a recent paper by Strohmer and Vershynin (J. Fourier Anal. Appl. 15:262-278, 2009) a "randomized kaczmarz algorithm" is proposed for solving consistent systems of linear equations {aOE (c) a (i) ,x >=b...
详细信息
In a recent paper by Strohmer and Vershynin (J. Fourier Anal. Appl. 15:262-278, 2009) a "randomized kaczmarz algorithm" is proposed for solving consistent systems of linear equations {aOE (c) a (i) ,x >=b (i) } (i=1) (m) . In that algorithm the next equation to be used in an iterative kaczmarz process is selected with a probability proportional to aEuro-a (i) aEuro-(2). The paper illustrates the superiority of this selection method for the reconstruction of a bandlimited function from its nonuniformly spaced sampling values. In this note we point out that the reported success of the algorithm of Strohmer and Vershynin in their numerical simulation depends on the specific choices that are made in translating the underlying problem, whose geometrical nature is "find a common point of a set of hyperplanes", into a system of algebraic equations. If this translation is carefully done, as in the numerical simulation provided by Strohmer and Vershynin for the reconstruction of a bandlimited function from its nonuniformly spaced sampling values, then indeed good performance may result. However, there will always be legitimate algebraic representations of the underlying problem (so that the set of solutions of the system of algebraic equations is exactly the set of points in the intersection of the hyperplanes), for which the selection method of Strohmer and Vershynin will perform in an inferior manner.
暂无评论