Non-rigid registration of 3D shapes is an essential task of increasing importance as commodity depth sensors become more widely available for scanning dynamic scenes. Non-rigid registration is much more challenging than rigid registration as it estimates a set of local transformations instead of a single global transformation, and hence is prone to the overfitting issue due to underdetermination. The common wisdom in previous methods is to impose an l2-norm regularization on the local transformation differences. However, the l2-norm regularization tends to bias the solution towards outliers and noise with heavy-tailed distribution, which is verified by the poor goodness- of-fit of the Gaussian distribution over transformation differences. On the contrary, Laplacian distribution fits well with the transformation differences, suggesting the use of a sparsity prior. We propose a sparse non-rigid registration (SNR) method with an l1-norm regularized model for transformation estimation, which is effectively solved by an alternate direction method (ADM) under the augmented Lagrangian framework. We also devise a multi-resolution scheme for robust and progressive registration. Results on both public datasets and our scanned datasets show the superiority of our method, particularly in handling large-scale deformations as well as outliers and noise.

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 Aot= B especially when Aot= B is known to be a subset of Aot= 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 Aot= B to each class of functions Aot= B , such that, to separate complexity classes Aot= B , it suffices to observe a change in" the number of holes", ie homology, in Aot= B as a subclass Aot= B of Aot= B is added to Aot= B . In other words, if the homologies of Aot= B and Aot= B are different, then Aot= B . We develop the underlying theory of functions based on combinatorial and homological commutative algebra and Stanley-Reisner theory, and recover Minsky and Papert's 1969 result that parity cannot be computed by nonmaximal degree polynomial threshold functions. In the process, we derive a" maximal principle" for polynomial threshold functions that is used to extend this result further to arbitrary symmetric functions. A surprising coincidence is demonstrated, where the maximal dimension of" holes" in Aot= B upper bounds the VC dimension of Aot= B , with equality for common computational cases such as the class of polynomial threshold functions or the class of linear functionals in Aot= B , or common algebraic cases such as when the Stanley-Reisner ring of Aot= B 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

Gapped domain walls, as topological line defects between 2+1D topologically ordered states, are examined. We provide simple criteria to determine the existence of gapped domain walls, which apply to both Abelian and non-Abelian topological orders. Our criteria also determine which 2+1D topological orders must have gapless edge modes, namely which 1+1D global gravitational anomalies ensure gaplessness. Furthermore, we introduce a new mathematical object, the tunneling matrix $W$, whose entries are the fusion-space dimensions $W_{ia}$, to label different types of gapped domain walls. Mathematically, we propose a classification of bimodule categories between modular tensor categories. By studying many examples, we find evidence that the tunneling matrices are powerful quantities to classify different types of gapped domain walls. Since a gapped boundary is a gapped domain wall between a bulk topological order and the vacuum, regarded as the trivial topological order, our theory of gapped domain walls inclusively contains the theory of gapped boundaries. In addition, we derive a topological ground state degeneracy formula, applied to arbitrary orientable spatial 2-manifolds with gapped domain walls, including closed 2-manifolds and open 2-manifolds with gapped boundaries.

Woodin has demonstrated that, in the presence of large cardinals, there is a single model of ZFC which is maximal for Π_{2}-sentences over the structure ($H$($ω$_{2}), ∈, NS_{$ω$1}), in the sense that its ($H$($ω$_{2}), ∈, NS_{$ω$1}) satisfies every Π_{2}-sentence$σ$for which ($H$($ω$_{2}), ∈, NS_{$ω$1}) ⊨$σ$can be forced by set-forcing. In this paper we answer a question of Woodin by showing that there are two Π_{2}-sentences over the structure ($H$($ω$_{2}), ∈,$ω$_{1}) which can each be forced to hold along with the continuum hypothesis, but whose conjunction implies $$ {2^{{{\aleph_0}}}}={2^{{{\aleph_1}}}} $$ . In the process we establish that there are two preservation theorems for not introducing new real numbers by a countable support iterated forcing which cannot be subsumed into a single preservation theorem.

No abstract uploaded!