This paper studies the problem of finding best rank-1 approximations for both symmetric and nonsymmetric tensors. For symmetric tensors, this is equivalent to optimizing homogeneous polynomials over unit spheres; for nonsymmetric tensors, this is equivalent to optimizing multiquadratic forms over multispheres. We propose semidefinite relaxations, based on sum of squares representations, to solve these polynomial optimization problems. Their special properties and structures are studied. In applications, the resulting semidefinite programs are often large scale. The recent Newton-CG augmented Lagrangian method by Zhao, Sun, and Toh [SIAM J. Optim., 20 (2010), pp. 1737–1765] is suitable for solving these semidefinite relaxations. Extensive numerical experiments are presented to show that this approach is efficient in getting best rank-1 approximations.

No abstract uploaded!

We propose a variational approach to obtain superresolution images from multiple low-resolution frames extracted from video clips. First the displacement between the lowresolution frames and the reference frame are computed by an optical flow algorithm. Then a low-rank model is used to construct the reference frame in high-resolution by incorporating the information of the low-resolution frames. The model has two terms: a 2-norm data fidelity term and a nuclear-norm regularization term. Alternating direction method of multipliers is used to solve the model. Comparison of our methods with other models on synthetic and real video clips show that our resulting images are more accurate with less artifacts. It also provides much finer and discernable details.

No abstract uploaded!

This paper studies the convergence of the adaptively iterative thresholding (AIT) algorithm for compressed sensing. We first introduce a generalized restricted isometry property (gRIP). Then, we prove that the AIT algorithm converges to the original sparse solution at a linear rate under a certain gRIP condition in the noise free case. While in the noisy case, its convergence rate is also linear until attaining a certain error bound. Moreover, as by-products, we also provide some sufficient conditions for the convergence of the AIT algorithm based on the two well-known properties, i.e., the coherence property and the restricted isometry property (RIP), respectively. It should be pointed out that such two properties are special cases of gRIP. The solid improvements on the theoretical results are demonstrated and compared with the known results. Finally, we provide a series of simulations to verify the correctness of the theoretical assertions as well as the effectiveness of the AIT algorithm.

Adult stem cells, which exist throughout the body, multiply by cell division to replenish dying cells or to promote regeneration to repair damaged tissues. To perform these functions during the lifetime of organs or tissues, stem cells need to maintain their populations in a faithful distribution of their epigenetic states, which are suscepti- ble to stochastic fluctuations during each cell division, unexpected injury, and potential genetic mutations that occur during many cell divisions. However, it remains unclear how the three processes of differentiation, proliferation, and apoptosis in regulating stem cells collectively manage these challenging tasks. Here, without consid- ering molecular details, we propose a genetic optimal control model for adult stem cell regeneration that includes the three fundamental processes, along with cell division and adaptation based on differ- ential fitnesses of phenotypes. In the model, stem cells with a distri- bution of epigenetic states are required to maximize expected performance after each cell division. We show that heteroge- neous proliferation that depends on the epigenetic states of stem cells can improve the maintenance of stem cell distributions to create balanced populations. A control strategy during each cell division leads to a feedback mechanism involving heterogeneous proliferation that can accelerate regeneration with less fluctuation in the stem cell population. When mutation is allowed, apoptosis evolves to maximize the performance during homeostasis after multiple cell divisions. The overall results highlight the importance of cross-talk between genetic and epigenetic regulation and the performance objectives during homeostasis in shaping a desirable heterogeneous distribution of stem cells in epigenetic states.

The stochastic gradient (SG) method can quickly solve a problem with a large number of components in the objective, or a stochastic optimization problem, to a moderate accuracy. The block coordinate descent/update (BCD) method, on the other hand, can quickly solve problems with multiple (blocks of) variables. This paper introduces a method that combines the great features of SG and BCD for problems with many components in the objective and with multiple (blocks of) variables. This paper proposes a block SG (BSG) method for both convex and nonconvex programs. BSG generalizes SG by updating all the blocks of variables in the Gauss–Seidel type (updating the current block depends on the previously updated block), in either a fixed or randomly shuffled order. Although BSG has slightly more work at each iteration, it typically outperforms SG because of BSG’s Gauss–Seidel updates and larger step sizes, the latter of which are determined by the smaller per-block Lipschitz constants. The convergence of BSG is established for both convex and nonconvex cases. In the convex case, BSG has the same order of convergence rate as SG. In the nonconvex case, its convergence is established in terms of the expected violation of a first-order optimality condition. In both cases our analysis is nontrivial since the typical unbiasedness assumption no longer holds. BSG is numerically evaluated on the following problems: stochastic least squares and logistic regression, which are convex, and low-rank tensor recovery and bilinear logistic regression, which are nonconvex. On the convex problems, BSG performed significantly better than SG. On the nonconvex problems, BSG significantly outperformed the deterministic BCD method because the latter tends to stagnate early near local minimizers. Overall, BSG inherits the benefits of both SG approximation and block coordinate updates and is especially useful for solving large-scale nonconvex problems.

No abstract uploaded!

A popular and classical method for finding the best rank one approximation of a real tensor is the higher order power method (HOPM). It is known in the literature that the iterative sequence generated by HOPM converges globally, while the convergence rate can be superlinear, linear or sublinear. In this paper, we examine the convergence rate of HOPM in solving the best rank one approximation problem of real tensors. We first show that the iterative sequence of HOPM always converges globally and provide an explicit eventual sublinear convergence rate. The sublinear convergence rate estimate is in terms of the dimension and the order of the underlying tensor space. Then, we examine the concept of nondegenerate singular vector tuples and show that, if the sequence of HOPM converges to a nondegenerate singular vector tuple, then the global convergence rate is R-linear. We show that, for almost all tensors (in the sense of Lebesgue measure), all the singular vector tuples are nondegenerate, and so, the HOPM “typically” exhibits global R-linear convergence rate. Moreover, without any regularity assumption, we establish that the sequence generated by HOPM always converges globally and R-linearly for orthogonally decomposable tensors with order at least 3. We achieved this by showing that each nonzero singular vector tuple of an orthogonally decomposable tensor with order at least 3 is nondegenerate.

No abstract uploaded!

No abstract uploaded!

We develop a generic game platform that can be used to model various real-world systems with multiple intelligent cloud-computing pools and parallel-queues for resources-competing users. Inside the platform, the software structure is modelled as Blockchain. All the users are associated with Big Data arrival streams whose random dynamics is modelled by triply stochastic renewal reward processes (TSRRPs). Each user may be served simultaneously by multiple pools while each pool with parallel- servers may also serve multi-users at the same time via smart policies in the Blockchain, e.g. a Nash equilibrium point myopically at each fixed time to a game-theoretic scheduling problem. To illustrate the effectiveness of our game platform, we model the performance measures of its internal data flow dynamics (queue length and workload processes) as reflecting diffusion with regime-switchings (RDRSs) under our scheduling policies. By RDRS models, we can prove our myopic game-theoretic policy to be an asymptotic Pareto minimal-dual-cost Nash equilibrium one globally over the whole time horizon to a randomly evolving dynamic game problem. Iterative schemes for simulating our multi-dimensional RDRS models are also developed with the support of numerical comparisons.

In this paper, we construct a new suboptimal filter by deriving the Ito's stochastic differential equations of the estimation of higher order central moments satisfy and imposing some conditions to form a closed system. The essentially infinite-dimensional cubic sensor problem has been investigated in detail numerically to illustrate the reasonableness of the imposed conditions, and the numerical experiments support our discussion. A 2-dimensional polynomial filtering problem has also been experimented.

A fundamental and very well studied region of the Erdős–Rényi process is the phase transition at$m$∼$n$/2 edges in which a giant component suddenly appears. We examine the process beginning with an initial graph. We further examine the Bohman–Frieze process in which edges between isolated vertices are more likely. While the positions of the phase transitions vary, the three processes belong, roughly speaking, to the same universality class. In particular, the growth of the giant component in the barely supercritical region is linear in all cases.

The Mumford–Shah model is one of the most important image segmentation models and has been studied extensively in the last twenty years. In this paper, we propose a two-stage segmentation method based on the Mumford–Shah model. The first stage of our method is to find a smooth solution g to a convex variant of the Mumford–Shah model. Once g is obtained, then in the second stage the segmentation is done by thresholding g into different phases. The thresholds can be given by the users or can be obtained automatically using any clustering methods. Because of the convexity of the model, g can be solved efficiently by techniques like the split-Bregman algorithm or the Chambolle–Pock method. We prove that our method is convergent and that the solution g is always unique. In our method, there is no need to specify the number of segments K (K ≥ 2) before finding g. We can obtain any K-phase segmentations by choosing (K − 1) thresholds after g is found in the first stage, and in the second stage there is no need to recompute g if the thresholds are changed to reveal different segmentation features in the image. Experimental results show that our two-stage method performs better than many standard two-phase or multiphase segmentation methods for very general images, including antimass, tubular, MRI, noisy, and blurry images.

No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

In this article, we propose two numerical methods, the Gaussian Process (GP) method and the Fourier Features (FF) algorithm, to solve mean field games (MFGs). The GP algorithm approximates the solution of a MFG with maximum a posteriori probability estimators of GPs conditioned on the partial differential equation (PDE) system of the MFG at a finite number of sample points. The main bottleneck of the GP method is to compute the inverse of a square gram matrix, whose size is proportional to the number of sample points. To improve the performance, we introduce the FF method, whose insight comes from the recent trend of approximating positive definite kernels with random Fourier features. The FF algorithm seeks approximated solutions in the space generated by sampled Fourier features. In the FF method, the size of the matrix to be inverted depends only on the number of Fourier features selected, which is much less than the size of sample points. Hence, the FF method reduces the precomputation time, saves the memory, and achieves comparable accuracy to the GP method. We give the existence and the convergence proofs for both algorithms. The convergence argument of the GP method does not depend on any monotonicity condition, which suggests the potential applications of the GP method to solve MFGs with non-monotone couplings in future work. We show the efficacy of our algorithms through experiments on a stationary MFG with a non-local coupling and on a time-dependent planning problem. We believe that the FF method can also serve as an alternative algorithm to solve general PDEs.

No abstract uploaded!

The aim of this paper is to provide a fast and efficient procedure for (real-time) target identification in imaging based on matching on a dictionary of precomputed generalized polarization tensors (GPTs). The approach is based on some important properties of the GPTs and new invariants. A new shape representation is given and numerically tested in the presence of measurement noise. The stability and resolution of the proposed identification algorithm is numerically quantified. We compare the proposed GPT-based shape representation with a moment-based one.

We study correlation bounds under pairwise independent distributions for functions with no large Fourier coefficients. Functions in which all Fourier coefficients are bounded by$δ$are called$δ$-$uniform$. The search for such bounds is motivated by their potential applicability to hardness of approximation, derandomization, and additive combinatorics.

In this paper, we study, for the first time, nonconvex minimax separable quadratic optimization problems with multiple separable quadratic constraints and their second-order cone programming (SOCP) relaxations. Under suitable conditions, we establish exact SOCP relaxation for minimax nonconvex separable quadratic programs. We show that various important classes of specially structured minimax quadratic optimization problems admit exact SOCP relaxations under easily verifiable conditions. These classes include some minimax extended trust-region problems, minimax uniform quadratic optimization problems, max dispersion problems, and some robust quadratic optimization problems under bounded data uncertainty. The present work shows that nonconvex minimax separable quadratic problems with quadratic constraints, which contain a hidden closed and convex epigraphical set, exhibit exact SOCP relaxations.

We propose an efficient threshold dynamics method for topology optimization for fluids modeled with the Stokes equation. The proposed algorithm is based on minimization of an objective energy function that consists of the dissipation power in the fluid and the perimeter approximated by nonlocal energy, subject to a fluid volume constraint and the incompressibility condition. We show that the minimization problem can be solved with an iterative scheme in which the Stokes equation is approximated by a Brinkman equation. The indicator functions of the fluid-solid regions are then updated according to simple convolutions followed by a thresholding step. We demonstrate mathematically that the iterative algorithm has the total energy decaying property. The proposed algorithm is simple and easy to implement. A simple adaptive time strategy is also used to accelerate the convergence of the iteration. Extensive numerical experiments in both two and three dimensions show that the proposed iteration algorithm is quite robust and converges in much fewer iterations and is more efficient than many existing methods.

In this paper we derive the stochastic differentials of the conditional central moments of the nonlinear filtering problems, especially those of the polynomial filtering problem, and develop a novel suboptimal method by solving this evolution equation. The basic idea is to augment the state of the original nonlinear system by including the original states' conditional central moments such that the augmented states form a so-called bilinear system after truncating. During our derivation, it is clear to see that the stochastic differentials of the conditional central moments of the linear filtering problem (i.e., $f$, $g$ and $h$ are all at most degree one polynomials) form a closed system automatically without truncation. This gives one reason for the existence of optimal filtering for linear problems. On the contrary, the conditional central moments form an infinite dimensional system, in general. To reduce it to a closed-form, we let all the high enough central moments to be zero, as one did in the Carleman approach \cite{GMP}. Consequently, a novel suboptimal method is developed by dealing with the bilinear system. Numerical simulation is performed for the cubic sensor problem to illustrate the accuracy and numerical stability.