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.
We present a class of iterative fully distributed fixed point methods to solve a system of linear equations, such that each agent in the network holds one or several of the equations of the system. ...Under a generic directed, strongly connected network, we prove a convergence result analogous to the one for fixed point methods in the classical, centralized, framework: the proposed method converges to the solution of the system of linear equations at a linear rate. We further explicitly quantify the rate in terms of the linear system and network parameters. Next, we show that the algorithm provably works under time-varying directed networks provided that the underlying graph is connected over bounded iteration intervals, and we establish a linear convergence rate for this setting as well. A set of numerical results is presented, demonstrating practical benefits of the method over existing alternatives.
Extensions of compressed sensing Tsaig, Yaakov; Donoho, David L.
Signal processing,
March 2006, 2006-03-00, Letnik:
86, Številka:
3
Journal Article
Recenzirano
We study the notion of compressed sensing (CS) as put forward by Donoho, Candes, Tao and others. The notion proposes a signal or image, unknown but supposed to be compressible by a known transform, ...(e.g. wavelet or Fourier), can be subjected to fewer measurements than the nominal number of data points, and yet be accurately reconstructed. The samples are nonadaptive and measure ‘random’ linear combinations of the transform coefficients. Approximate reconstruction is obtained by solving for the transform coefficients consistent with measured data and having the smallest possible ℓ1 norm.
We present initial ‘proof-of-concept’ examples in the favorable case where the vast majority of the transform coefficients are zero. We continue with a series of numerical experiments, for the setting of ℓp-sparsity, in which the object has all coefficients nonzero, but the coefficients obey an ℓp bound, for some p∈(0,1. The reconstruction errors obey the inequalities paralleling the theory, seemingly with well-behaved constants.
We report that several workable families of ‘random’ linear combinations all behave equivalently, including random spherical, random signs, partial Fourier and partial Hadamard.
We next consider how these ideas can be used to model problems in spectroscopy and image processing, and in synthetic examples see that the reconstructions from CS are often visually “noisy”. To suppress this noise we post-process using translation-invariant denoising, and find the visual appearance considerably improved.
We also consider a multiscale deployment of compressed sensing, in which various scales are segregated and CS applied separately to each; this gives much better quality reconstructions than a literal deployment of the CS methodology.
These results show that, when appropriately deployed in a favorable setting, the CS framework is able to save significantly over traditional sampling, and there are many useful extensions of the basic idea.
For purpose of solving system of linear equations (SoLE) more efficiently, a fast convergent gradient neural network (FCGNN) model is designed and discussed in this paper. Different from the design ...of the conventional gradient neural network (CGNN), the design of the FCGNN model is based on a nonlinear activation function, and thus the better convergence speed can be reached. In addition, the convergence upper bound of the FCGNN model is estimated and provided in details. Simulative results validate the superiority of the FCGNN model, as compared to the CGNN model for finding SoLE.
•A fast convergent gradient neural network is proposed for linear equations.•The convergence time upper bound of the proposed model is estimated.•The error bound is equal to zero theoretically after convergence time.
We consider the binomial random set model np where each element in {1,…,n} is chosen independently with probability p:=p(n). We show that for essentially all regimes of p and very general conditions ...for a matrix A and a column vector b, the count of specific integer solutions to the system of linear equations Ax=b with the entries of x in np follows a (conveniently rescaled) normal limiting distribution. This applies among others to the number of solutions with every variable having a different value, as well as to a broader class of so-called non-trivial solutions in homogeneous strictly balanced systems. Our proof relies on the delicate linear algebraic study both of the subjacent matrices and the corresponding ranks of certain submatrices, together with the application of the method of moments in probability theory.
Abstract Fundamental matrix operations and solving linear systems of equations are ubiquitous in scientific investigations. Using the ‘sender-receiver’ model, we propose quantum algorithms for matrix ...operations such as matrix-vector product, matrix-matrix product, the sum of two matrices, and the calculation of determinant and inverse matrix. We encode the matrix entries into the probability amplitudes of the pure initial states of senders. After applying proper unitary transformation to the complete quantum system, the desired result can be found in certain blocks of the receiver’s density matrix. These quantum protocols can be used as subroutines in other quantum schemes. Furthermore, we present an alternative quantum algorithm for solving linear systems of equations.
Resumen En el presente trabajo investigamos la utilidad didáctica de usar parámetros como variables de naturaleza dual (variables activas o inactivas), así como la actualización de cinco profesores ...mexicanos en este saber. En esta actualización se analizaron sistemas de ecuaciones lineales (SEL) con dos ecuaciones y tres incógnitas que tienen infinitas soluciones. Para ello propusimos, vía internet, cinco artefactos semióticos: 1. una definición, 2. la inclusión del parámetro en el SEL, 3. el cálculo de soluciones, 4. representaciones gráficas y 5. la aplicación a un problema en contexto. Los resultados revelaron la pertinencia de la introducción del parámetro mediante este proceso y, además, los profesores lograron un control sobre las soluciones válidas de entre las infinitas del sistema planteado. Para algunos profesores, la estrategia y el papel del parámetro fue sólo un método más que se agrega a los ya conocidos; sin embargo, para otros, permitió dar una explicación a la relación entre la variable y el parámetro, así como la posibilidad del uso controlado de las infinitas soluciones.
Abstract In the present work, we investigate the didactic usefulness of using parameters as variables of dual nature (active or inactive variables), as well as the actualization of five Mexican teachers in this knowledge. In this actualization we analyzed systems of linear equations (SLE) with two equations and three unknowns that had infinite solutions. For this purpose, we proposed, via the Internet, five semiotic artifacts: 1. A definition, 2. The inclusion of the parameter in the SLE, 3. The calculation of solutions, 4. Graphical representations, and 5. The application to a problem in context. The results revealed the relevance of introducing the parameter through this process and, in addition, the teachers achieved control over the valid solutions among the infinite ones of the system posed. For some teachers, the strategy and the role of the parameter was just one more method to be added to those already known; however, for others, it allowed an explanation of the relationship between the variable and the parameter, as well as the possibility of the controlled use of the infinite solutions.
PDF
