No abstract uploaded!

In this paper, we analyze the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function, φ(x0, . . . , x p, y), subject to coupled linear equality constraints. Our ADMM updates each of the primal variables x0, . . . , x p, y, followed by updating the dual variable.We separate the variable y from xi ’s as it has a special role in our analysis. The developed convergence guarantee covers a variety of nonconvex functions such as piecewise linear functions, lq quasi-norm, Schatten-q quasi-norm (0 < q < 1), minimax concave penalty (MCP), and smoothly clipped absolute deviation penalty. It also allows nonconvex constraints such as compact manifolds (e.g., spherical, Stiefel, and Grassman manifolds) and linear complementarity constraints. Also, the x0-block can be almost any lower semi-continuous function. By applying our analysis, we show, for the first time, that several ADMM algorithms applied to solve nonconvex models in statistical learning, optimization on manifold, and matrix decomposition are guaranteed to converge. Our results provide sufficient conditions for ADMM to converge on (convex or nonconvex) monotropic programs with three or more blocks, as they are special cases of our model. ADMM has been regarded as a variant to the augmented Lagrangian method (ALM). We present a simple example to illustrate how ADMM converges but ALM diverges with bounded penalty parameter β. Indicated by this example and other analysis in this paper, ADMM might be a better choice than ALM for some nonconvex nonsmooth problems, because ADMM is not only easier to implement, it is also more likely to converge for the concerned scenarios.

In computational complexity, a complexity class is given by a set of problems or functions, and a basic challenge is to show separations of complexity classes A!= B especially when A is known to be a subset of B. In this paper we introduce a homological theory of functions that can be used to establish complexity separations, while also providing other interesting consequences. We propose to associate a topological space S_A to each class of functions A, such that, to separate complexity classes A from a superclass B', it suffices to observe a change in" the number of holes", ie homology, in S_A as a subclass B of B'is added to A. In other words, if the homologies of S_A and S_ {A union B} are different, then A!= B'. We develop the underlying theory of functions based on homological commutative algebra and Stanley-Reisner theory, and prove a" maximal principle" for polynomial threshold functions that is used to recover Aspnes, Beigel, Furst, and Rudich's characterization of the polynomial threshold degree of symmetric functions. A surprising coincidence is demonstrated, where, roughly speaking, the maximal dimension of" holes" in S_A upper bounds the VC dimension of A, with equality for common computational cases such as the class of polynomial threshold functions or the class of linear functionals over the finite field of 2 elements, or common algebraic cases such as when the Stanley-Reisner ring of S_A is Cohen-Macaulay. As another interesting application of our theory, we prove a result that a priori has nothing to do with complexity separation: it characterizes when a vector subspace intersects the positive cone, in terms of homological

We present a novel solution to automatic semantic modeling of indoor scenes from a sparse set of low-quality RGB-D images. Such data presents challenges due to noise, low resolution, occlusion and missing depth information. We exploit the knowledge in a scene database containing 100s of indoor scenes with over 10,000 manually segmented and labeled mesh models of objects. In seconds, we output a visually plausible 3D scene, adapting these models and their parts to fit the input scans. Contextual relationships learned from the database are used to constrain reconstruction, ensuring semantic compatibility between both object models and parts. Small objects and objects with incomplete depth information which are difficult to recover reliably are processed with a two-stage approach. Major objects are recognized first, providing a known scene structure. 2D contour-based model retrieval is then used to recover smaller objects. Evaluations using our own data and two public datasets show that our approach can model typical real-world indoor scenes efficiently and robustly.

The bran fraction of wheat grain is known to contain significant quantities of bioactive components. This study evaluated the potential of solid-state yeast fermentation to improve the health beneficial properties of wheat bran, including extractable antioxidant properties, protein contents, and soluble and insoluble fiber compositions. Three commercial food grade yeast preparations were evaluated in the study along with the effects of yeast dose, treatment time, and their interaction with the beneficial components. Solid-state yeast treatments were able to significantly increase releasable antioxidant properties ranging from 28 to 65, from 0 to 20, from 13 to 19, from 0 to 25, from 50 to 100, and from 3 to 333% for scavenging capacities against peroxyl (ORAC), ABTS cation, DPPH and hydroxyl radicals, total phenolic contents (TPC), and phenolic acids, respectively. Yeast treatment increased protein content 11-12% but did not significantly alter the fiber composition of wheat bran. Effects of solid-state yeast treatment on both ORAC and TPC of wheat bran were altered by yeast dose, treatment time, and their interaction. Results suggest that solid-state yeast treatment may be a commercially viable postharvest procedure for improving the health beneficial properties of wheat bran and other wheat-based food ingredients.