Program on March 16th
Secant Variable Projection Method for Solving Nonnegative Separable Least Squares Problems. Time: 10:30-10:55 (UTC+9). Speaker: Wei Xu. - RYERSON UNIVERSITY. Abstract: The variable projection method is a classical and efficient method for solving separable nonlinear least squares (SNLLS) problem- s.  However, it is hard to handle the constrained SNLLS problems since the explicit form of Jacobian matrix is required in each iteration. In this paper, we propose a secant variable projection (SVP) method, which em- ploys a rank-one update to estimate the Jacobian matrices.  The main advantages of our method are efficiency and ease of applicability to con- strained SNLLS problems. The local convergence of our SVP method is also analyzed. Finally, some data fitting and image processing problems are solved to compare the performance of our proposed method with the classical variable projection method. Numerical results illustrate the effi- ciency and stability of our proposed SVP method in solving the SNLLS problems arising from the blind deconvolution problems. An extension of asymptotic duality in SDP and its implication to the convergence theory of infeasible interior-point algorithms. Time: 10:55-11:20 (UTC+9). Speaker: Takashi Tsuchiya. - NATIONAL GRADUATE INSTITUTE FOR POLICY STUDIES. Abstract: Consider a primal-dual pair of SDP and assume that both pri- mal and dual are either weakly feasible or weakly infeasible. Under such circumstances, the pair might have a nonzero duality gap. Nevertheless, there are arbitrary small perturbations which makes the perturbed primal- dual pair strongly feasible thus zeroing the duality gap.  We conduct a perturbation analysis on the pair.  We fix two positive definite matrices, I p and I d , say, (typically the identity matrices), and perturb the original primal and dual problem by α and β , respectively to recover interior fea- sibility, where and are positive numbers.  Then we analyze the behavior of the optimal value of the perturbed pair when the perturbation is reduced to zero keeping the proportion of α and β constant. It will be shown that the optimal value of the perturbed problem converges to a value between the primal and dual optimal values of the original problem. Furthermore, we demonstrate that the infeasible interior-point algorithm for SDP gen- erates a sequence converging to a number between the primal and dual optimal values, even in the presence of a nonzero duality gap. This is a joint work with Bruno F. Lourenco, Masakazu Muramatsu and Takayuki Okuno. Efficient Nonnegative Tensor Ring Decomposition via A New Algorithm Framework. Time: 11:20-11:45 (UTC+9). Speaker: Ning Zheng. - THE INSTITUTE OF STATISTICAL MATHEMATICS. Abstract: Tensor decomposition has been widely used for the dimen- sional reduction and extraction of the meaningful latent features of high dimensional tensor data. In many applications, the underlying data en- semble is nonnegative and consequently the nonnegative tensor decom- position is proposed to achieve additive parts-based representation and to learn more physically interpretable results. As the corresponding ten- sor optimization problem has computational difficulty due to nonconvex, together with sparse, smooth, graph based Tikhonov regularization, the construction and analysis of the reliable, efficient and robust algorithms are required.  Under the framework of block coordinate descent method, we aim to present a new iterative algorithm which is based on the modu- lus type variable transformation. The theoretical analysis of the proposed method is discussed. Numerical experiments including the synthetic da- ta and image data show the efficiency and superiority of the proposed method comparing with the state-of-the-art methods.
Behaviour of GMRES and block GMRES for matrices with multiple and clustered eigenvalues. Time:  13:15-13:40 (UTC+9). Speaker: Zeyu Liao. - THE GRADUATE UNIVERSITY FOR ADVANCED STUDIES (SOKENDAI). Abstract: We will study the numerical behaviour of GMRES and block GMRES for coefficient matrices with multiple and clustered eigenvalues and try to analyze it. A preconditioned Krylov subspace iterative method for indefinite matrices arising from beating heart simulations. Time: 13:40-14:05 (UTC+9). Speaker: Takumi Washio. - UT-HEART INC., THE UNIVERSITY of TOKYO. Abstract: In our beating heart simulations based on a fluid-structure cou- pling finite element model, several factors generate indefinite matrices from Lagrange multiplier approaches dealing with the constraints by the incompressibility of continuums and the contacts between surfaces.  In this talk, the strategies in constructing the preconditioner, the iterative method, and the parallelization for our problem are introduced. Further- more, missing theories for estimating the efficiency of our preconditioner and the convergence of the Krylov subspace iterative method are also discussed. PMHSS iteration method and preconditioners for Stokes control PDE-constrained optimization problems. Time:  14:05-14:30 (UTC+9). Speaker: Zeng-Qi Wang. - SHANGHAI JIAO TONG UNIVERSITY. Abstract: The preconditioned modified Hermitian/skew-Hermitian s- plitting (PMHSS) iteration method and the corresponding precondition- ing technique can achieve satisfactory results for solving optimal con- trol problems governed by Poisson's equation. We explore the feasibility of such a method and preconditioner for solving optimization problems constrained by the more complicated Stokes system.  Theoretical results demonstrate that the PMHSS iteration method is convergent because the spectral radius of the iterative matrix is less than sqrt2/2. Additionally, the PMHSS preconditioner still clusters eigenvalues on a unitary segmen- t. It guarantees that the convergence of the PMHSS iteration method and preconditioning is independent of not only discretizing mesh size, but also of the Tikhonov regularization parameter. A more effective precon- ditioner is proposed based on the PMHSS preconditioner. The proposed preconditioner avoids the inner iterations when solving saddle point sys- tems appearing in the generalized residual equations.  Furthermore, it is still convergent and maintains its independence of parameter and mesh size.
Verifying eigenvalues of generalized Hermitian eigenproblems using contour intergrals. Time:  14:45-15:10 (UTC+9). Speaker: Keiichi Morikuni. - UNIVERSITY OF TSUKUBA. Abstract: We consider verifying all eigenvalues in a prescribed inter- val of a generalized Hermitian eigenproblem. A given eigenproblem can be reduced by a contour integral method into a generalized eigenprob- lem consisting of complex moments.  This kind of method motivated us to develop verification methods that are efficient in parallel.  Evaluating all errors in computing the complex moments, we develop verification methods for the eigenproblems.  Based on the truncation errors for the trapezoidal rule of numerical quadrature, we derive a numerically com- putable enclosure of the complex moment. Then, we take into accoun- t numerical errors of the quadrature and rigorously enclose the moment matrices. Our error bounds are interval arithmetic-friendly and enables to determine the required number of quadrature points beforehand, accord- ing to the degree of precision one needs and the cost one can pay.  Each quadrature point gives rise to a linear system, and its structure enables us to develop an efficient technique to verify the approximate solution, which does not need a numerical matrix inverse. Numerical experiments show that the proposed method outperforms a standard method and infer that the proposed method will be potentially efficient in parallel. This is joint work with Akira Imakura and Akitoshi Takayasu. Structured generalized eigenvalue condition numbers for parameterized quasiseparable matrices. Time: 15:10-15:35 (UTC+9). Speaker: Huaian Diao. - NORTHEAST NORMAL UNIVERSITY. Abstract: In this talk, when A and B are {1;1}-quasiseparable matri- ces, we consider the structured generalized relative eigenvalue condition numbers of the pair ( A,B ) with respect to relative perturbations of the parameters defining A and B in the quasiseparable and the Givens-vector representations of these matrices.  A general expression is derived for the condition number of the generalized eigenvalue problems of the pair (A,B), where A and B are any differentiable function of a vector of pa- rameters with respect to perturbations of such parameters. Moreover, the explicit expressions of the corresponding structured condition numbers with respect to the quasiseparable and Givens-vector representation vi- a tangents for {1;1}-quasiseparable matrices are derived.  Our proposed condition numbers can be computed efficiently by utilizing the recur- sive structure of quasiseparable matrices.  We investigate relationships between various condition numbers of structured generalized eigenvalue problem when A and B are {1;1}-quasiseparable matrices.  Numerical results show that there are situations in which the unstructured condition number can be much larger than the structured ones. Time:  15:35-16:00 (UTC+9). Speaker: Michael Kwok-Po Ng. - The UNIVERSITY OF HONG KONG. Abstract: In this talk, we study low rank matrix approximation (NLR- M) for nonnegative matrices arising from many data mining and pattern recognition applications.  Our approach is different from classical non- negative matrix factorization (NMF) which has been studied for some time. For a given nonnegative matrix, the usual NMF approach is to deter- mine two nonnegative low rank matrices such that the distance between their product and the given nonnegative matrix is as small as possible. However, the proposed NLRM approach is to determine a nonnegative low rank matrix such that the distance between such matrix and the given nonnegative matrix is as small as possible.  There are two advantages. (i) The minimized distance can be smaller.  (ii) The proposed method can identify important singular basis vectors, while this information may not be obtained in the classical NMF. Numerical results are reported to demonstrate the performance of the proposed method.  Several extensions and research works are also presented.
Time: 16:15-16:40 (UTC+9). Speaker: José Mas Marí. - UNIVERSITAT POLITÈCNICA DE VALÈNCIA. Abstract: Preconditioners are used to accelerate the convergence of iter- ative linear solvers.  When the linear system Ax = b , changes a little, let’s say to (A + B)x = c, where B has low rank, the preconditioner obtained from A loses effectivity. Instead of computing a new preconditioner from scratch we proposed to update it by bordering the coefficient matrix, and adding new entries to the right-hand side, in such a way that the bordered system is equivalent to the system (A + B)x = c. Then the old precondi- toner can be reused and updated computing who the added blocks should be incorporated to the preconditioner of the bordered matrix.  In addi- tion, the application of the preconditioner should be changed to include the effect of the updating.  Moreover, the technique can be used to deal with other situations as rank deficiency of the coefficient matrix, which prevent to obtain a preconditioner using factorization techniques.  Also, if the coefficient matrix has a low-rank skew symmetric part, this technique allows to compute a preconditioner for the symmetric part and then in- clude the skew-symmetric in the preconditioning step. In this talk I will review the technique and show some applications to the above mentioned problems. Implementation of interior-point methods for LP based on Krylov subspace iterative solvers with inner-iteration preconditioning. Time: 16:40-17:05 (UTC+9). Speaker:  Yiran Cui. - TBA. Abstract: We apply novel inner-iteration preconditioned Krylov sub- space methods to the interior-point (IP) algorithm for linear programming (LP). Inner-iteration preconditioners proposed by Morikuni and Haya- mi enable us to overcome the severe ill-conditioning of linear equations solved in the final phase of IP iterations. The Krylov subspace methods do not suffer from rank-deficiency and therefore no preprocessing is nec- essary even if rows of the constraint matrix are not linearly independent. Via these methods, a new IP recurrence is proposed to omit one matrix- vector product per step. Extensive numerical experiments are conducted over diverse instances of 140 LP problems including the Netlib, QAPLIB, Mittelmann and Atomizer Basis Pursuit collections.  The largest prob- lem has 434,580 unknowns.  It turns out that our implementation is more robust than the standard public domain solvers SeDuMi, SDPT3 and the LSMR iterative solver in PDCO without increasing CPU time. The proposed IP method based on iterative solvers succeeds in solving a fairly large number of LP instances from benchmark libraries under the standard stopping criteria.  The work also presents a fairly extensive benchmark test for several renowned solvers including direct and iterative solvers.
Algorithms and Analysis Program on March 17th
Modulus-based iterative methods for constrained ℓ p − ℓ q minimization. Time: 10:30-10:55 (UTC+9). Speaker: Lothar Reichel. - KENT STATE UNIVERSITY. Abstract:  We describe computational methods for the solution of ℓ ρ − ℓ q minimization problems of the form min x {||Ax − b|| b + μ||Lx||g} with 0 < q < 1 and 0 < p < 2. Here A and L are matrices, x and b are vectors, and the parameter μ > 0 balances the influence of the two terms.  Ap- plications include image restoration and parameter estimation in linear regression. In the latter application, the method is capable of simulta- neously producing sparse estimates and dealing with outliers and heavy- tailed error distributions. On convergence of the dynamic mode decomposition for noisy datasets. Time: 10:55-11:20 (UTC+9). Speaker: Kensuke Aishima. - HOSEI UNIVERSITY. Abstract: Dynamic mode decomposition (DMD) is an efficient method for time series analysis. From a viewpoint of matrix computations, the D- MD computes eigenvalues and the corresponding eigenvectors of a given matrix associated with time series data.  The basic tools are the singu- lar value decomposition (SVD) and the Rayleigh-Ritz procedure. In this talk, we consider a random matrix due to noisy datasets. In such a case, the DMD computes perturbed eigenpairs including the noise.  To reduce the errors, the total least squares method is introduced in the DMD in an implicit form.  This algorithm has an excellent performance in terms of the noise cancellation.  My recent study focuses on theoretical justifica- tion of such kinds of DMD and its generalization. The main result is con- vergence theory in the probabilistic sense. More specifically, for sample data gradually increasing, it can be proved that the computed eigenpairs contaminated with the random noise converge to the exact ones under a statistical model. In this talk, I will talk about this statistical model and the strong convergence of the computed eigenpairs. Convergence of GMRES and RRGMRES methods for symmetric singular systems. Time: 11:20-11:45 (UTC+9). Speaker: Kota Sugihara. - NATIONAL INSTITUTE OF INFORMATICS. Abstract: Consider the symmetric singular systems which arise, for in- stance, in the discretization of partial differential equations for electro- magnetic fields using the edge-based finite element method. When the right-hand side vector is not in the range space of the coeffi- cient matrix, we will compare the convergence of GMRES and Range Re- stricted GMRES(RRGMRES) methods, which are robust against round- ing errors, by numerical experiments and the theory. We will report the reason that GMRES does not sometimes converge enough unlike the convergence theory about the GMRES method.  We will analyze the convergence of the method theoretically, which we have proposed as the solver for the least squares problems when the Hessen- berg matrix becomes ill-conditioned, and report the numerical results. Finally, we will show that the range space component of the RRGMRES methods is equivalent to the GMRES methods applied to the nonsingular systems, and will analyze its convergence.
Preconditioning techniques in GMRES methods for least squares problems. Time:  13:15-13:40 (UTC+9). Speaker: Jun-Feng Yin. - TONGJI UNIVERSITY. Abstract: In order to speedup the convergence of GMRES methods for least square problems, different preconditioners including diagonal scal- ing, robust incomplete factorization, incomplete Givens orthogonaliza- tion and Greville's method are studied and analyzed in details, as well as the theoretical properties and implementations.  Numerical experiments show they are efficient for the solution of least square problem of suitable size. For large sparse problems, flexible preconditioners updated with the process of the outer iteration are suggested. On Partially Randomized Extended Kaczmarz Method for Inconsistent Linear Systems. Time: 13:40-14:05 (UTC+9). Speaker: Wen-Ting Wu. - BEIJING INSTITUTE OF TECHNOLOGY. Abstract: For solving large sparse, overdetermined, and inconsistent system of linear equations by iteration methods, by further reconstruct- ing the randomized extended Kaczmarz method proposed by Zouzias and Freris in 2013 (SIAM J. Matrix Anal.  Appl.  34(2013), 773 – 793), we propose a partially randomized extended Kaczmarz method.  When the coefficient matrix is assumed to be of full column rank, we prove the convergence and derive an upper bound for the expected convergence rate of the partially randomized extended Kaczmarz method. This bound could be smaller than that of the randomized extended Kaczmarz method under certain conditions. Moreover, with numerical results we show that the partially randomized extended Kaczmarz method can be much more effective than the randomized extended Kaczmarz method. Solving Multi-Linear Systems with Nonsingular Tensor. Time:  14:05-14:30 (UTC+9). Speaker:  Yi-Min Wei. - FUDAN UNIVERSITY. Abstract: This talk is concerned with solving some structured multi- linear systems, especially focusing on the equations whose coefficient tensors are M-tensors, or called M-equations for short.  We prove that a nonsingular M-equation with a positive right-hand side always has a unique positive solution.  Several iterative algorithms are proposed for solving multi-linear nonsingular M-equations, generalizing the classical iterative methods and the Newton method for linear systems.  Further- more, we apply theM-equations to some nonlinear differential equations and the inverse iteration for spectral radii of nonnegative tensors.
High-Resolution Phase Reconstruction in Ground-based Astronomy. Time:  14:45-15:10 (UTC+9). Speaker: Raymond Chan. - CITY UNIVERSITY OF HONG KONG. Abstract: Adaptive optics is a commonly used technique to correct the phase distortions caused by the Earth's atmosphere to improve the image quality of the ground-based imaging systems.  However, the observed images still suffer from the blur caused by the adaptive optics residual wavefront.  We propose a model for reconstructing the residual phase in high-resolution from a sequence of low-resolution deformable mirror da- ta.  Our model is based on the turbulence statistics and the Taylor frozen flow hypothesis.  A tomography problem for the phase distortions from different altitudes is solved to get a high-quality phase reconstruction. The associated joint optimization problem was solved by an alternating minimization method which results in a high-resolution reconstruction al- gorithm with adaptive wind velocities. Numerical simulations are carried out to show the effectiveness of our approach. Joint work with Rihuan Ke (University of Cambridge), Roland Wagn- er, and Ronny Ramlau (RICAM). GMRES on singular systems revisited. Time:  15:10-15:40 (UTC+9). Speaker: Ken Hayami. - NATIONAL INSTITUTE OF INFORMATICS. Abstract: We will reconsider the definition of breakdown of GMRES for singular systems in Brown and Walker (1997).  We will also correct the proof of the convergence of GMRES for inconsistent singular systems in Hayami and Sugihara, M. (2011). Kaczmarz-type inner-iteration preconditioned flexible GMRES methods for consistent linear systems. Time: 15:40-16:05 (UTC+9). Speaker:  Yi-Shu Du. - TONGJI UNIVERSITY. Abstract: We propose using greedy and randomized Kaczmarz inner- iterations as preconditioners for the right-preconditioned flexible GM- RES method to solve consistent linear systems, with a parameter tun- ing strategy for adjusting the number of inner iterations and the relax- ation parameter.  We also present theoretical justifications of the right- preconditioned flexible GMRES for solving consistent linear system- s.  Numerical experiments on overdetermined and underdetermined lin- ear systems show that the proposed method is superior to the GMRES method preconditioned by NE-SOR inner iterations in terms of total CPU time.
Unmatched Projector/Backprojector Pairs and Algebraic Iterative Reconstruction. Time: 16:20-16:45 (UTC+9). Speaker: Per Christian Hansen. - TECHNICAL UNIVERSITY OF DENMARK. Abstract:  Algebraic iterative reconstruction methods - such as ART (Kaczmarz), SART, and SIRT - are popular for CT reconstruction; they adapt to any scanner geometry and handle limited-angle and limited-data problems.  The iterative methods utilize projection and backprojection operations in each iteration.  We represent the projection by a matrix A while, in principle, we represent the backprojection by B = A T (the trans- pose of A). When the iterative methods are implemented with a focus on computa- tional efficiency, different discretization schemes are used for the forward projection and the backprojection.  Hence, there is a mismatch between the backprojection matrix B and the transposed A T of the forward projec- tion matrix. The use of such an unmatched pair has two consequences: the accuracy (compared to when using a matched pair) deteriorates, and the iteration may fail to converge. In this survey talk, I illustrate these issues with recent theoretical and computational results, and I present a few novel approaches to "fixing" the non-convergence - either by modifying the iterative method or by using the AB- and BA-GMRES methods. This is joint work with Yiqiu Dong, Tommy Elfving, Ken Hayami, Michiel Hochstenbach, Keiichi Morikuni, and Nicolai Riis. Randomized algorithms for matrix problems. Time: 16:45-17:10 (UTC+9). Speaker: Yuji Nakatsukasa. - OXFORD UNIVERSITY. Abstract: Randomized low-rank matrix approximation has become an extremely successful approach for efficiently computing a low-rank ap- proximation of matrices.  In particular the paper by Halko, Martinsson, and Tropp (SIREV 2011) contains extensive analysis, and has made it a very popular method.  The typical complexity for a rank-r approx- imation of m × n matrices is O(mnlogn + (m + n)r 2 ) for dense matri- ces.  In this talk I will first describe a fast and stable algorithm requiring O(mnlogn + r 3 ) flops.  I also plan to report on recent developments in randomized algorithms:  (a subset of) efficient randomized rank estima- tion, linear solvers, QR factorization, and approximating matrices whose singular values do not decay.