Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian

Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian: "

Abstract

In analogy to the absolute algebraic connectivity of Fiedler, we study the problem of minimizing the maximum eigenvalue of
the Laplacian of a graph by redistributing the edge weights. Via semidefinite duality this leads to a graph realization problem
in which nodes should be placed as close as possible to the origin while adjacent nodes must keep a distance of at least one.
We prove three main results for a slightly generalized form of this embedding problem. First, given a set of vertices partitioning
the graph into several or just one part, the barycenter of each part is embedded on the same side of the affine hull of the
set as the origin. Second, there is an optimal realization of dimension at most the tree-width of the graph plus one and this
bound is best possible in general. Finally, bipartite graphs possess a one dimensional optimal embedding.

• Content Type Journal Article
• Category Full Length Paper
• DOI 10.1007/s10107-010-0344-z
• Authors
  
  
  • Frank Göring, Technische Universität Chemnitz Fakultät für Mathematik 09107 Chemnitz Germany
  • Christoph Helmberg, Technische Universität Chemnitz Fakultät für Mathematik 09107 Chemnitz Germany
  • Susanna Reiss, Technische Universität Chemnitz Fakultät für Mathematik 09107 Chemnitz Germany
  
  

• Journal Mathematical Programming
• Online ISSN 1436-4646
• Print ISSN 0025-5610

"

Randomized Kaczmarz solver for noisy linear systems

Randomized Kaczmarz solver for noisy linear systems: "

Abstract

The Kaczmarz method is an iterative algorithm for solving systems of linear equations Ax=b. Theoretical convergence rates for this algorithm were largely unknown until recently when work was done on a randomized
version of the algorithm. It was proved that for overdetermined systems, the randomized Kaczmarz method converges with expected
exponential rate, independent of the number of equations in the system. Here we analyze the case where the system Ax=b is corrupted by noise, so we consider the system Ax≈b+r where r is an arbitrary error vector. We prove that in this noisy version, the randomized method reaches an error threshold dependent
on the matrix A with the same rate as in the error-free case. We provide examples showing our results are sharp in the general context.

• Content Type Journal Article
• DOI 10.1007/s10543-010-0265-5
• Authors
  
  
  • Deanna Needell, Stanford University Department of Statistics Stanford CA 94305-4065 USA
  
  

• Journal BIT Numerical Mathematics
• Online ISSN 1572-9125
• Print ISSN 0006-3835

"

Fast transforms for high order boundary conditions in deconvolution problems

Fast transforms for high order boundary conditions in deconvolution problems: "

Abstract

We study strategies to increase the precision in deconvolution models, while maintaining the complexity of the related numerical
linear algebra procedures (matrix-vector product, linear system solution, computation of eigenvalues, etc.) of the same order
of the celebrated fast Fourier transform. The key idea is the choice of a suitable functional basis to represent signals and
images. Starting from an analysis of the spectral decomposition of blurring matrices associated to the antireflective boundary
conditions introduced in Serra Capizzano (SIAM J. Sci. Comput. 25(3):1307–1325, 2003), we extend the model for preserving polynomials of higher degree and fast computations also in the nonsymmetric case.

We apply the proposed model to Tikhonov regularization with smoothing norms and the generalized cross validation in order
to choose the regularization parameter. A selection of numerical experiments shows the effectiveness of the proposed techniques.

• Content Type Journal Article
• DOI 10.1007/s10543-010-0266-4
• Authors
  
  
  • Marco Donatelli, Università dell’Insubria Dipartimento di Fisica e Matematica Via Valleggio 11 22100 Como Italy
  
  

• Journal BIT Numerical Mathematics
• Online ISSN 1572-9125
• Print ISSN 0006-3835

"