A Unitary Extension Principle for Shearlet Systems. (arXiv:0912.4529v1 [math.NA])

In this paper, we first introduce the concept of an adaptive MRA (AMRA)
structure which is a variant of the classical MRA structure suited to the main
goal of a fast flexible decomposition strategy adapted to the data at each
decomposition level. We then study this novel methodology for the general case
of affine-like systems, and derive a Unitary Extension Principle (UEP) for
filter design. Finally, we apply our results to the directional representation
system of shearlets. This leads to a comprehensive theory for fast
decomposition algorithms associated with shearlet systems which encompasses
tight shearlet frames with spatially compactly supported generators within such
an AMRA structure. Also shearlet-like systems associated with parabolic scaling
and unimodular matrices optimally close to rotation as well as 3D shearlet
systems are studied within this framework.

Published by

Original source : http://arxiv.org/abs/0912.4529...

Fast Alternating Linearization Methods for Minimizing the Sum of Two Convex Functions. (arXiv:0912.4571v1 [math.OC])

Splitting and alternating direction methods have been widely used for solving
convex optimization problems. We present in this paper two first-order
alternating linearization algorithms based on variable splitting and
alternating linearization techniques for minimizing the sum of two convex
functions. We prove that the number of iterations needed by the first algorithm
is $O(1/epsilon)$ to obtain an $epsilon$-optimal solution. The second
algorithm is an accelerated version of the first one, where the complexity
result is improved to $O(1/sqrt{epsilon})$, while the computational effort
required at each iteration is almost unchanged. Our algorithms and complexity
results can also be extended to more general problems involving linear
operators. Algorithms in this paper are Gauss-Seidel type methods, so they are
different with the ones proposed by Goldfarb and Ma in [12] where the
algorithms are all Jacobi type methods. Preliminary numerical results are
reported to support our theoretical conclusions and demonstrate the practical
potential of our algorithms.

Published by

Original source : http://arxiv.org/abs/0912.4571...

Fast Multiple Splitting Algorithms for Convex Optimization. (arXiv:0912.4570v1 [math.OC])

We present in this paper two different classes of general $K$-splitting
algorithms for solving convex optimization problems. We prove that the number
of iterations needed by the first class of algorithms to obtain an
$epsilon$-optimal solution is $O(1/epsilon)$. The algorithms in the second
class are accelerated versions of those in the first class, where the
complexity result is improved to $O(1/sqrt{epsilon})$ while the computational
effort required at each iteration is almost unchanged. The algorithms are also
extended to solving convex optimization problems involving linear operators
such as those that arise in variational formulations of partial differential
equations and in optimal control problems. To the best of our knowledge, the
complexity results presented in this paper are the first ones of this type that
have been given for splitting and alternating direction type methods. Moreover,
all algorithms proposed in this paper are parallelizable, which makes them
particularly attractive for solving large-scale problems.

Published by

Original source : http://arxiv.org/abs/0912.4570...