Reconstruction of n-dimensional convex bodies from surface tensors

In this paper, we derive uniqueness and stability results for surface tensors. Further, we develop two algorithms that reconstruct shape of n-dimensional convex bodies. One algorithm requires knowledge of a finite number of surface tensors, whereas the other algorithm is based on noisy measurements of a finite number of harmonic intrinsic volumes. The derived stability results ensure consistency of the two algorithms. Examples that illustrate the feasibility of the algorithms are presented.     

Integral geometry of tensor valuations

We prove a complete set of integral geometric formulas of Crofton type (involving integrations over affine Grassmannians) for the Minkowski tensors of convex bodies. Minkowski tensors are the natural tensor valued valuations generalizing the intrinsic volumes (or Minkowski functionals) of convex bodies. By Hadwiger's general integral geometric theorem, the Crofton formulas yield also kinematic formulas for Minkowski tensors. The explicit calculations of integrals over affine Grassmannians require several integral geometric and combinatorial identities. The latter are derived with the help of Zeilberger's algorithm.     

Local tensor valuations on convex polytopes

Local versions of the Minkowski tensors of convex bodies in $n$ -dimensional Euclidean space are introduced. An extension of Hadwiger’s characterization theorem for the intrinsic volumes, due to Alesker, states that the continuous, isometry covariant valuations on the space of convex bodies with values in the vector space of symmetric $p$ -tensors are linear combinations of modified Minkowski tensors. We ask for a local analogue of this characterization, and we prove a classification result for local tensor valuations on polytopes, without a continuity assumption.     

Local Tensor Valuations

The local Minkowski tensors are valuations on the space of convex bodies in Euclidean space with values in a space of tensor measures. They generalize at the same time the intrinsic volumes, the curvature measures and the isometry covariant Minkowski tensors that were introduced by McMullen and characterized by Alesker. In analogy to the characterization theorems of Hadwiger and Alesker, we give here a complete classification of all locally defined tensor measures on convex bodies that share with the local Minkowski tensors the basic geometric properties of isometry covariance and weak continuity.     

Surface tensor estimation from linear sections

From Crofton's formula for Minkowski tensors we derive stereological estimators of translation invariant surface tensors of convex bodies in the n‐dimensional Euclidean space. The estimators are based on one‐dimensional linear sections. In a design based setting we suggest three types of estimators. These are based on isotropic uniform random lines, vertical sections, and non‐isotropic random lines, respectively. Further, we derive estimators of the specific surface tensors associated with a stationary process of convex particles in the model based setting.     

Interpolation of harmonic functions based on Radon projections

We consider an algebraic method for reconstruction of a harmonic function in the unit disk via a finite number of values of its Radon projections. The approach is to seek a harmonic polynomial which matches given values of Radon projections along some chords of the unit circle. We prove an analogue of the famous Marr’s formula for computing the Radon projection of the basis orthogonal polynomials in our setting of harmonic polynomials. Using this result, we show unique solvability for a family of schemes where all chords are chosen at equal distance to the origin. For the special case of chords forming a regular convex polygon, we prove error estimates on the unit circle and in the unit disk. We present an efficient reconstruction algorithm which is robust with respect to noise in the input data and provide numerical examples.     

Localization from Incomplete Noisy Distance Measurements

We consider the problem of positioning a cloud of points in the Euclidean space ? ^d , using noisy measurements of a subset of pairwise distances. This task has applications in various areas, such as sensor network localization and reconstruction of protein conformations from NMR measurements. It is also closely related to dimensionality reduction problems and manifold learning, where the goal is to learn the underlying global geometry of a data set using local (or partial) metric information. Here we propose a reconstruction algorithm based on semidefinite programming. For a random geometric graph model and uniformly bounded noise, we provide a precise characterization of the algorithm’s performance: in the noiseless case, we find a radius r ₀ beyond which the algorithm reconstructs the exact positions (up to rigid transformations). In the presence of noise, we obtain upper and lower bounds on the reconstruction error that match up to a factor that depends only on the dimension d, and the average degree of the nodes in the graph.     

Local Stereology of Tensors of Convex Bodies

In this paper, we present local stereological estimators of Minkowski tensors defined on convex bodies in ? ^d . Special cases cover a number of well-known local stereological estimators of volume and surface area in ?³, but the general set-up also provides new local stereological estimators of various types of centres of gravity and tensors of rank two. Rank two tensors can be represented as ellipsoids and contain information about shape and orientation. The performance of some of the estimators of centres of gravity and volume tensors of rank two is investigated by simulation.     

l k,s -Singular values and spectral radius of rectangular tensors

The real rectangular tensors arise from the strong ellipticity condition problem in solid mechanics and the entanglement problem in quantum physics. In this paper, we study the singular values/vectors problem of real nonnegative partially symmetric rectangular tensors. We first introduce the concepts of l ^k,s -singular values/vectors of real partially symmetric rectangular tensors. Then, based upon the presented properties of l ^k,s -singular values /vectors, some properties of the related l ^k,s -spectral radius are discussed. Furthermore, we prove two analogs of Perron-Frobenius theorem and weak Perron-Frobenius theorem for real nonnegative partially symmetric rectangular tensors.     

On computing minimal <Emphasis Type="Italic">H</Emphasis>-eigenvalue of sign-structured tensors

Finding the minimal H-eigenvalue of tensors is an important topic in tensor computation and numerical multilinear algebra. This paper is devoted to a sum-of-squares (SOS) algorithm for computing the minimal H-eigenvalues of tensors with some sign structures called extended essentially nonnegative tensors (EEN-tensors), which includes nonnegative tensors as a subclass. In the even-order symmetric case, we first discuss the positive semi-definiteness of EEN-tensors, and show that a positive semi-definite EEN-tensor is a nonnegative tensor or an M-tensor or the sum of a nonnegative tensor and an M-tensor, then we establish a checkable sufficient condition for the SOS decomposition of EEN-tensors. Finally, we present an efficient algorithm to compute the minimal H-eigenvalues of even-order symmetric EEN-tensors based on the SOS decomposition. Numerical experiments are given to show the efficiency of the proposed algorithm.     

L(μ)-averaging domains

In this paper we first introduce L^s(μ)-averaging domains which are generalizations of L^s-averaging domains introduced by S.G. Staples. We characterize L^s(μ)-averaging domains using the quasihyperbolic metric. As applications, we prove norm inequalities for conjugate A-harmonic tensors in L^s(μ)-averaging domains which can be considered as generalizations of the Hardy and Littlewood theorem for conjugate harmonic functions. Finally, we give applications to quasiconformal and quasiregular mappings.     

On the Error Estimate of the Harmonic B_z Algorithm in MREIT from Noisy Magnetic Flux Field

Magnetic resonance electrical impedance tomography(MREIT, for short) is a new medical imaging technique developed recently to visualize the cross-section conductivity of biologic tissues. A new MREIT image reconstruction method called harmonic Bz algorithm was proposed in 2002 with the measurement of Bz that is a single component of an induced magnetic flux density subject to an injection current. The key idea is to solve a nonlinear integral equation by some iteration process. This paper deals with the convergence analysis as well as the error estimate for noisy input data Bz, which is the practical situation for MREIT. By analyzing the iteration process containing the Laplacian operation on the input magnetic field rigorously, the authors give the error estimate for the iterative solution in terms of the noisy level δ and the regularizing scheme for determiningΔBz approximately from the noisy input data. The regularizing scheme for computing the Laplacian from noisy input data is proposed with error analysis. Our results provide both the theoretical basis and the implementable scheme for evaluating the reconstruction accuracy using harmonic Bz algorithm with practical measurement data containing noise.     

基于截断加权基追踪模型的迭代支撑探测算法

迭代支撑探测算法是基于截断的基追踪(Basis Pursuit,BP)模型的一种l_1最小化信号重构算法,它可以实现信号的快速重构并且所需要的观测值比经典的L1算法以及迭代加权L1算法更少.本文针对非零元具有快速退化分布性质的稀疏信号,提出了一种改进算法一一基于截断的加权BP模型的迭代支撑探测算法.在迭代的过程中,改进的算法探测原信号支撑集中元素的同时调整重构模型的权值,使得重构模型更有利于实现信号的精确重构.根据所考虑的信号的非零元具有快速退化分布性质这样的先验信息,利用阈值法则探测原信号支撑集中的元素.最后通过Matlab数值实验实现了算法,验证了基于截断的加权BP模型的迭代支撑探测算法比迭代加权L1算法需要的观测值更少,并且比迭代加权L1算法以及传统的迭代支撑探测算法需要更少的重构时间就可以实现信号的精确重构.     

An algorithm for surface reconstruction from planar contours using smoothing splines

This paper presents a fast algorithm for constructing a smooth three-dimensional surface over a set of cross-sectional contours. We assume that these sections are perpendicular to the z-axis and first consider the case that the surface can be represented in cylindrical coordinates. An approximation is then determined for r(θ, z) by using tensor product splines which satisfy certain boundary constraints. The algorithm is an extension of an existing semi-automatic surface fitting algorithm. The knots of the spline are chosen automatically but a single parameter is expected to control the tradeoff between closeness of fit and smoothness of fit.Both open and closed surfaces can be represented. In particular we demonstrate the use of a non-linear transformation for obtaining smooth closed surfaces.The algorithm can easily be extended to the reconstruction of surfaces which cannot be represented in cylindrical coordinates. A number of applications are also briefly discussed such as the calculation of volumes and the intersection with other surfaces. We have applied the method in practice to obtain a 3-D integrated image of the cerebral blood vessels and CT view of tumor for stereotactic neurosurgery.     

An iterative row-action method for interval convex programming

The iterative primal-dual method of Bregman for solving linearly constrained convex programming problems, which utilizes nonorthogonal projections onto hyperplanes, is represented in a compact form, and a complete proof of convergence is given for an almost cyclic control of the method. Based on this, a new algorithm for solving interval convex programming problems, i.e., problems of the form minf(x), subject to γ≤Ax≤δ, is proposed. For a certain family of functionsf(x), which includes the norm ∥x∥ and thex logx entropy function, convergence is proved. The present row-action method is particularly suitable for handling problems in which the matrixA is large (or huge) and sparse.     

A global harmonic Arnoldi method for large non-Hermitian eigenproblems with an application to multiple eigenvalue problems

The global Arnoldi method can be used to compute exterior eigenpairs of a large non-Hermitian matrix A, but it does not work well for interior eigenvalue problems. Based on the global Arnoldi process that generates an F-orthonormal basis of a matrix Krylov subspace, we propose a global harmonic Arnoldi method for computing certain harmonic F-Ritz pairs that are used to approximate some interior eigenpairs. We propose computing the F-Rayleigh quotients of the large non-Hermitian matrix with respect to harmonic F-Ritz vectors and taking them as new approximate eigenvalues. They are better and more reliable than the harmonic F-Ritz values. The global harmonic Arnoldi method inherits convergence properties of the harmonic Arnoldi method applied to a larger matrix whose distinct eigenvalues are the same as those of the original given matrix. Some properties of the harmonic F-Ritz vectors are presented. As an application, assuming that A is diagonalizable, we show that the global harmonic Arnoldi method is able to solve multiple eigenvalue problems both in theory and in practice. To be practical, we develop an implicitly restarted global harmonic Arnoldi algorithm with certain harmonic F-shifts suggested. In particular, this algorithm can be adaptively used to solve multiple eigenvalue problems. Numerical experiments show that the algorithm is efficient for the eigenproblem and is reliable for quite ill-conditioned multiple eigenproblems.     

Extending the QCR method to general mixed-integer programs

Let (MQP) be a general mixed integer quadratic program that consists of minimizing a quadratic function subject to linear constraints. In this paper, we present a convex reformulation of (MQP), i.e. we reformulate (MQP) into an equivalent program, with a convex objective function. Such a reformulation can be solved by a standard solver that uses a branch and bound algorithm. We prove that our reformulation is the best one within a convex reformulation scheme, from the continuous relaxation point of view. This reformulation, that we call MIQCR (Mixed Integer Quadratic Convex Reformulation), is based on the solution of an SDP relaxation of (MQP). Computational experiences are carried out with instances of (MQP) including one equality constraint or one inequality constraint. The results show that most of the considered instances with up to 40 variables can be solved in 1?h of CPU time by a standard solver.     

Simple bounds for recovering low-complexity models

This note presents a unified analysis of the recovery of simple objects from random linear measurements. When the linear functionals are Gaussian, we show that an s-sparse vector in ${\mathbb{R}^n}$ can be efficiently recovered from 2s log n measurements with high probability and a rank r, n × n matrix can be efficiently recovered from r(6n ? 5r) measurements with high probability. For sparse vectors, this is within an additive factor of the best known nonasymptotic bounds. For low-rank matrices, this matches the best known bounds. We present a parallel analysis for block-sparse vectors obtaining similarly tight bounds. In the case of sparse and block-sparse signals, we additionally demonstrate that our bounds are only slightly weakened when the measurement map is a random sign matrix. Our results are based on analyzing a particular dual point which certifies optimality conditions of the respective convex programming problem. Our calculations rely only on standard large deviation inequalities and our analysis is self-contained.     

On the determination of convex bodies by projection and girth functions

It is known that (in the sense of Baire category) most n-dimensional convex bodies are uniquely determined, up to translation or reflection, by the i-dimensional volumes of the orthogonal projections on i-planes, provided that i ∈ {2,…, n ? 2}. This result is strengthened by showing that small sets of projections are sufficient for such determinations. The proof yields an extension of the result, where volumes are generalized to intrinsic volumes.     

Global convergence properties of two modified BFGS-type methods

This article studies a modified BFGS algorithm for solving smooth unconstrained strongly convex minimization problem. The modified BFGS method is based on the new quasi-Newton equation B_k+1s_k=yk where y_k*, =yk + A_ks_k andA _k is a matrix. Wei, Li and Qi [WLQ] have proven that the average performance of two of those algorithms is better than that of the classical one. In this paper, we prove the global convergence of these algorithms associated to a general line search rule.