Given
This content will become publicly available on August 1, 2024
Variational quasi-harmonic maps for computing diffeomorphisms
Computation of injective (or inversion-free) maps is a key task in geometry processing, physical simulation, and shape optimization. Despite being a longstanding problem, it remains challenging due to its highly nonconvex and combinatoric nature. We propose computation of
- Award ID(s):
- 1838071
- NSF-PAR ID:
- 10483958
- Publisher / Repository:
- Association for Computing Machinery
- Date Published:
- Journal Name:
- ACM Transactions on Graphics
- Volume:
- 42
- Issue:
- 4
- ISSN:
- 0730-0301
- Page Range / eLocation ID:
- 1 to 26
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract n disjoint intervals on together withn functions , , and an matrix , the problem is to find anL 2solution , , to the linear system , where , is a matrix of finite Hilbert transforms with defined on , and is a matrix of the corresponding characteristic functions on . Since we can interpret , as a generalized multi‐interval finite Hilbert transform, we call the formula for the solution as “the inversion formula” and the necessary and sufficient conditions for the existence of a solution as the “range conditions”. In this paper we derive the explicit inversion formula and the range conditions in two specific cases: a) the matrix Θ is symmetric and positive definite, and; b) all the entries of Θ are equal to one. We also prove the uniqueness of solution, that is, that our transform is injective. In the case a), that is, when the matrix Θ is positive definite, the inversion formula is given in terms of the solution of the associated matrix Riemann–Hilbert Problem. In the case b) we reduce the multi interval problem to a problem onn copies of and then express our answers in terms of the Fourier transform. We also discuss other cases of the matrix Θ. -
Lossy trapdoor functions, introduced by Peikert and Waters (STOC ’08), can be initialized in one of two indistinguishable modes: in injective mode, the function preserves all information about its input, and can be efficiently inverted given a trapdoor, while in lossy mode, the function loses some information about its input. Such functions have found countless applications in cryptography, and can be constructed from a variety of Cryptomania assumptions. In this work, we introduce targeted lossy functions (TLFs), which relax lossy trapdoor functions along two orthogonal dimensions. Firstly, they do not require an inversion trapdoor in injective mode. Secondly, the lossy mode of the function is initialized with some target input, and the function is only required to lose information about this particular target. The injective and lossy modes should be indistinguishable even given the target. We construct TLFs from Minicrypt assumptions, namely, injective pseudorandom generators, or even one-way functions under a natural relaxation of injectivity. We then generalize TLFs to incorporate branches, and construct all-injective-but-one and all-lossy-but-one variants. We show a wide variety of applications of targeted lossy functions. In several cases, we get the first Minicrypt constructions of primitives that were previously only known under Cryptomania assumptions. Our applications include: Pseudo-entropy functions from one-way functions. Deterministic leakage-resilient message-authentication codes and improved leakage-resilient symmetric-key encryption from one-way functions. Extractors for extractor-dependent sources from one-way functions. Selective-opening secure symmetric-key encryption from one-way functions. A new construction of CCA PKE from (exponentially secure) trapdoor functions and injective pseudorandom generators. We also discuss a fascinating connection to distributed point functions.more » « less
-
Many machine learning techniques sacrifice convenient computational structures to gain estimation robustness and modeling flexibility. However, by exploring the modeling structures, we find these ``sacrifices'' do not always require more computational efforts. To shed light on such a ``free-lunch'' phenomenon, we study the square-root-Lasso (SQRT-Lasso) type regression problem. Specifically, we show that the nonsmooth loss functions of SQRT-Lasso type regression ease tuning effort and gain adaptivity to inhomogeneous noise, but is not necessarily more challenging than Lasso in computation. We can directly apply proximal algorithms (e.g. proximal gradient descent, proximal Newton, and proximal quasi-Newton algorithms) without worrying about the nonsmoothness of the loss function. Theoretically, we prove that the proximal algorithms combined with the pathwise optimization scheme enjoy fast convergence guarantees with high probability. Numerical results are provided to support our theory.more » « less
-
Brehm, Christoph ; Pandya, Shishir (Ed.)We have derived a 3-D kinetic-based discrete dynamic system (DDS) from the lattice Boltzmann equation (LBE) for incompressible flows through a Galerkin procedure. Expressed by a poor-man lattice Boltzmann equation (PMLBE), it involves five bifurcation parameters including relaxation time from the LBE, splitting factor of large and sub-grid motion scales, and wavevector components from the Fourier space. Numerical experiments have shown that the DDS can capture laminar behaviors of periodic, subharmonic, n-period, and quasi-periodic and turbulent behaviors of noisy periodic with harmonic, noisy subharmonic, noisy quasi-periodic, and broadband power spectra. In this work, we investigated the effects of bifurcation parameters on the capturing of the laminar and turbulent flows in terms of the convergence of time series and the pattern of power spectra. We have found that the 2nd order and 3rd order PMLBEs are both able to capture laminar and turbulent flow behaviors but the 2nd order DDS performs better with lower computation cost and more flow behaviors captured. With the specified ranges of the bifurcation parameters, we have identified two optimal bifurcation parameter sets for laminar and turbulent behaviors. Beyond this work, we are exploring the regime maps for a deeper understanding of the contributions of the bifurcation parameters to the capturing of laminar and turbulent behaviors. Surrogate models (to replace the PMLBE) are being developed using deep learning techniques to overcome the overwhelming computation cost for the regime maps. Meanwhile, the DDS is being employed in the large eddy simulation of turbulent pulsatile flows to provide dynamic sub-grid scale information.more » « less
-
We propose quasi-harmonic weights for interpolating geometric data, which are orders of magnitude faster to compute than state-of-the-art. Currently, interpolation (or, skinning) weights are obtained by solving large-scale constrained optimization problems with explicit constraints to suppress oscillative patterns, yielding smooth weights only after a substantial amount of computation time. As an alternative, our weights are obtained as minima of an unconstrained problem that can be optimized quickly using straightforward numerical techniques. We consider weights that can be obtained as solutions to a parameterized family of second-order elliptic partial differential equations. By leveraging the maximum principle and careful parameterization, we pose weight computation as an inverse problem of recovering optimal anisotropic diffusivity tensors. In addition, we provide a customized ADAM solver that significantly reduces the number of gradient steps; our solver only requires inverting tens of linear systems that share the same sparsity pattern. Overall, our approach achieves orders of magnitude acceleration compared to previous methods, allowing weight computation in near real-time.more » « less
