Primal and dual predicted decrease approximation methods

We introduce the notion of predicted decrease approximation (PDA) for constrained convex optimization, a flexible framework which includes as special cases known algorithms such as generalized conditional gradient, proximal gradient, greedy coordinate descent for separable constraints and working set methods for linear equality constraints with bounds. The new scheme allows the development of a unified convergence analysis for these methods. We further consider a partially strongly convex nonsmooth model and show that dual application of PDA-based methods yields new sublinear convergence rate estimates in terms of both primal and dual objectives. As an example of an application, we provide an explicit working set selection rule for SMO-type methods for training the support vector machine with an improved primal convergence analysis.     

Penrose-type inequalities with a Euclidean background

The Riemannian Penrose inequality (RPI) bounds from below the ADM mass of asymptotically flat manifolds of nonnegative scalar curvature in terms of the total area of all outermost compact minimal surfaces. The general form of the RPI is currently known for manifolds of dimension up to seven. In the present work, we prove a Penrose-like inequality that is valid in all dimensions, for conformally flat manifolds. Our inequality treats the area contributions of the minimal surfaces in a more favorable way than the RPI, at the expense of using the smaller Euclidean area (rather than the intrinsic area). We give an example in which our estimate is sharper than the RPI when many minimal surfaces are present. We do not require the minimal surfaces to be outermost. We also generalize the technique to allow for metrics conformal to a scalar-flat (not necessarily Euclidean) background and prove a Penrose-type inequality without an assumption on the sign of scalar curvature. Finally, we derive a new lower bound for the ADM mass of a conformally flat, asymptotically flat manifold containing any number of zero area singularities.     

A note on the DP-chromatic number of complete bipartite graphs

DP-coloring (also called correspondence coloring) is a generalization of list coloring recently introduced by Dvo?ák and Postle. Several known bounds for the list chromatic number of a graph $G$, ${\chi }_{?}\left(G\right)$, also hold for the DP-chromatic number of $G$, ${\chi }_{DP}\left(G\right)$. On the other hand, there are several properties of the DP-chromatic number that show that it differs with the list chromatic number. In this note we show one such property. It is well known that ${\chi }_{?}\left(K_{k,t}\right)=k+1$ if and only if $t\ge k^k$. We show that ${\chi }_{DP}\left(K_{k,t}\right)=k+1$ if $t\ge 1+(k^k∕k!)(log(k!)+1)$, and we show that ${\chi }_{DP}\left(K_{k,t}\right)<k+1$ if $t<k^k∕k!$.     

On the log-concavity of Hilbert series of Veronese subrings and Ehrhart series

For every positive integer n, consider the linear operator U _n on polynomials of degree at most d with integer coefficients defined as follows: if we write ${\frac{h(t)}{(1 - t)^{d + 1}}=\sum_{m \geq 0} g(m) \, t^{m}}For every positive integer n, consider the linear operator U _n on polynomials of degree at most d with integer coefficients defined as follows: if we write \frach(t)(1 - t)^{d + 1}=?_{m 3 0} g(m)  t^m{\frac{h(t)}{(1 - t)^{d + 1}}=\sum_{m \geq 0} g(m) \, t^{m}} , for some polynomial g(m) with rational coefficients, then \fracU_nh(t)(1- t)^d+1 = ?_{m 3 0}g(nm)  t^m{\frac{{\rm{U}}_{n}h(t)}{(1- t)^{d+1}} = \sum_{m \geq 0}g(nm) \, t^{m}} . We show that there exists a positive integer n _d , depending only on d, such that if h(t) is a polynomial of degree at most d with nonnegative integer coefficients and h(0) = 1, then for n ≥ n _d , U _n h(t) has simple, real, negative roots and positive, strictly log concave and strictly unimodal coefficients. Applications are given to Ehrhart δ-polynomials and unimodular triangulations of dilations of lattice polytopes, as well as Hilbert series of Veronese subrings of Cohen–Macauley graded rings.     

Pan-H-Linked Graphs

Let H be a multigraph, possibly containing loops. An H-subdivision is any simple graph obtained by replacing the edges of H with paths of arbitrary length. Let H be an arbitrary multigraph of order k, size m, n ₀(H) isolated vertices and n ₁(H) vertices of degree one. In Gould and Whalen (Graphs Comb. 23:165–182, 2007) it was shown that if G is a simple graph of order n containing an H-subdivision H{\mathcal{H}} and d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}}, then G contains a spanning H-subdivision with the same ground set as H{\mathcal{H}} . As a corollary to this result, the authors were able to obtain Dirac’s famed theorem on hamiltonian graphs; namely that if G is a graph of order n ≥ 3 with d(G) 3 \fracn2{\delta(G)\ge\frac{n}{2}} , then G is hamiltonian. Bondy (J. Comb. Theory Ser. B 11:80–84, 1971) extended Dirac’s theorem by showing that if G satisfied the condition d(G) 3 \fracn2{\delta(G) \ge \frac{n}{2}} then G was either pancyclic or a complete bipartite graph. In this paper, we extend the result from Gould and Whalen (Graphs Comb. 23:165–182, 2007) in a similar manner. An H-subdivision H{\mathcal{H}} in G is 1-extendible if there exists an H-subdivision H^*{\mathcal{H}^{*}} with the same ground set as H{\mathcal{H}} and |H^*| = |H| + 1{|\mathcal{H}^{*}| = |\mathcal{H}| + 1} . If every H-subdivision in G is 1-extendible, then G is pan-H-linked. We demonstrate that if H is sufficiently dense and G is a graph of large enough order n such that d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}} , then G is pan-H-linked. This result is sharp.     

A sequential parametric convex approximation method with applications to nonconvex truss topology design problems

We describe a general scheme for solving nonconvex optimization problems, where in each iteration the nonconvex feasible set is approximated by an inner convex approximation. The latter is defined using an upper bound on the nonconvex constraint functions. Under appropriate conditions, a monotone convergence to a KKT point is established. The scheme is applied to truss topology design (TTD) problems, where the nonconvex constraints are associated with bounds on displacements and stresses. It is shown that the approximate convex problem solved at each inner iteration can be cast as a conic quadratic programming problem, hence large scale TTD problems can be efficiently solved by the proposed method.     

Normal and pathological NCAT image and phantom data based on physiologically realistic left ventricle finite-element models

The four-dimensional (4-D) NURBS-based cardiac-torso (NCAT) phantom, which provides a realistic model of the normal human anatomy and cardiac and respiratory motions, is used in medical imaging research to evaluate and improve imaging devices and techniques, especially dynamic cardiac applications. One limitation of the phantom is that it lacks the ability to accurately simulate altered functions of the heart that result from cardiac pathologies such as coronary artery disease (CAD). The goal of this work was to enhance the 4-D NCAT phantom by incorporating a physiologically based, finite-element (FE) mechanical model of the left ventricle (LV) to simulate both normal and abnormal cardiac motions. The geometry of the FE mechanical model was based on gated high-resolution X-ray multislice computed tomography (MSCT) data of a healthy male subject. The myocardial wall was represented as a transversely isotropic hyperelastic material, with the fiber angle varying from -90 degrees at the epicardial surface, through 0 degrees at the midwall, to 90 degrees at the endocardial surface. A time-varying elastance model was used to simulate fiber contraction, and physiological intraventricular systolic pressure-time curves were applied to simulate the cardiac motion over the entire cardiac cycle. To demonstrate the ability of the FE mechanical model to accurately simulate the normal cardiac motion as well as the abnormal motions indicative of CAD, a normal case and two pathologic cases were simulated and analyzed. In the first pathologic model, a subendocardial anterior ischemic region was defined. A second model was created with a transmural ischemic region defined in the same location. The FE-based deformations were incorporated into the 4-D NCAT cardiac model through the control points that define the cardiac structures in the phantom which were set to move according to the predictions of the mechanical model. A simulation study was performed using the FE-NCAT combination to investigate how the differences in contractile function between the subendocardial and transmural infarcts manifest themselves in myocardial Single photon emission computed tomography (SPECT) images. The normal FE model produced strain distributions that were consistent with those reported in the literature and a motion consistent with that defined in the normal 4-D NCAT beating heart model based on tagged magnetic resonance imaging (MRI) data. The addition of a subendocardial ischemic region changed the average transmural circumferential strain from a contractile value of -0.09 to a tensile value of 0.02. The addition of a transmural ischemic region changed average circumferential strain to a value of 0.13, which is consistent with data reported in the literature. Model results demonstrated differences in contractile function between subendocardial and transmural infarcts and how these differences in function are documented in simulated myocardial SPECT images produced using the 4-D NCAT phantom. Compared with the original NCAT beating heart model, the FE mechanical model produced a more accurate simulation for the cardiac motion abnormalities. Such a model, when incorporated into the 4-D NCAT phantom, has great potential for use in cardiac imaging research. With its enhanced physiologically based cardiac model, the 4-D NCAT phantom can be used to simulate realistic, predictive imaging data of a patient population with varying whole-body anatomy and with varying healthy and diseased states of the heart that will provide a known truth from which to evaluate and improve existing and emerging 4-D imaging techniques used in the diagnosis of cardiac disease.     

Pose estimation of known objects during transmission tomographic image reconstruction

We address the problem of image formation in transmission tomography when metal objects of known composition and shape, but unknown pose, are present in the scan subject. Using an alternating minimization (AM) algorithm, derived from a model in which the detected data are viewed as Poisson-distributed photon counts, we seek to eliminate the streaking artifacts commonly seen in filtered back projection images containing high-contrast objects. We show that this algorithm, which minimizes the I-divergence (or equivalently, maximizes the log-likelihood) between the measured data and model-based estimates of the means of the data, converges much faster when knowledge of the high-density materials (such as brachytherapy applicators or prosthetic implants) is exploited. The algorithm incorporates a steepest descent-based method to find the position and orientation (collectively called the pose) of the known objects. This pose is then used to constrain the image pixels to their known attenuation values, or, for example, to form a mask on the "missing" projection data in the shadow of the objects. Results from two-dimensional simulations are shown in this paper. The extension of the model and methods used to three dimensions is outlined.     

Fourier-based forward and back-projectors in iterative fan-beam tomographic image reconstruction

Fourier-based forward and back-projection methods can reduce computation in iterative tomographic image reconstruction. Recently, an optimized nonuniform fast Fourier transform (NUFFT) approach was shown to yield accurate parallel-beam projections. In this paper, we extend the NUFFT approach to describe an O (N2 log N) projector/backprojector pair for fan-beam transmission tomography. Simulations and experiments with real CT data show that fan-beam Fourier-based forward and back-projection methods can reduce computation for iterative reconstruction while still providing accuracy comparable to their O (N3) space-based counterparts.