In pure integer linear programming it is often desirable to work with polyhedra that are full-dimensional, and it is well known that it is possible to reduce any polyhedron to a full-dimensional one in polynomial time. More precisely, using the Hermite normal form, it is possible to map a non full-dimensional polyhedron to a full-dimensional isomorphic one in a lower-dimensional space, while preserving integer vectors. In this paper, we extend the above result simultaneously in two directions. First, we consider mixed integer vectors instead of integer vectors, by leveraging on the concept of "integer reflexive generalized inverse." Second, we replace polyhedra with convex quadratic sets, which are sets obtained from polyhedra by enforcing one additional convex quadratic inequality. We study structural properties of convex quadratic sets, and utilize them to obtain polynomial time algorithms to recognize full-dimensional convex quadratic sets, and to find an affine function that maps a non full-dimensional convex quadratic set to a full-dimensional isomorphic one in a lower-dimensional space, while preserving mixed integer vectors. We showcase the applicability and the potential impact of these results by showing that they can be used to prove that mixed integer convex quadratic programming is fixed parameter tractable with parameter the number of integer variables. Our algorithm unifies and extends the known polynomial time solvability of pure integer convex quadratic programming in fixed dimension and of convex quadratic programming.
相關內容
This work presents an abstract framework for the design, implementation, and analysis of the multiscale spectral generalized finite element method (MS-GFEM), a particular numerical multiscale method originally proposed in [I. Babuska and R. Lipton, Multiscale Model.\;\,Simul., 9 (2011), pp.~373--406]. MS-GFEM is a partition of unity method employing optimal local approximation spaces constructed from local spectral problems. We establish a general local approximation theory demonstrating exponential convergence with respect to local degrees of freedom under certain assumptions, with explicit dependence on key problem parameters. Our framework applies to a broad class of multiscale PDEs with $L^{\infty}$-coefficients in both continuous and discrete, finite element settings, including highly indefinite problems (convection-dominated diffusion, as well as the high-frequency Helmholtz, Maxwell and elastic wave equations with impedance boundary conditions), and higher-order problems. Notably, we prove a local convergence rate of $O(e^{-cn^{1/d}})$ for MS-GFEM for all these problems, improving upon the $O(e^{-cn^{1/(d+1)}})$ rate shown by Babuska and Lipton. Moreover, based on the abstract local approximation theory for MS-GFEM, we establish a unified framework for showing low-rank approximations to multiscale PDEs. This framework applies to the aforementioned problems, proving that the associated Green's functions admit an $O(|\log\epsilon|^{d})$-term separable approximation on well-separated domains with error $\epsilon>0$. Our analysis improves and generalizes the result in [M. Bebendorf and W. Hackbusch, Numerische Mathematik, 95 (2003), pp.~1-28] where an $O(|\log\epsilon|^{d+1})$-term separable approximation was proved for Poisson-type problems.
In many circumstances given an ordered sequence of one or more types of elements/ symbols, the objective is to determine any existence of randomness in occurrence of one of the elements,say type 1 element. Such a method can be useful in determining existence of any non-random pattern in the wins or loses of a player in a series of games played. Existing methods of tests based on total number of runs or tests based on length of longest run (Mosteller (1941)) can be used for testing the null hypothesis of randomness in the entire sequence, and not a specific type of element. Additionally, the Runs Test tends to show results contradictory to the intuition visualised by the graphs of say, win proportions over time due to method used in computation of runs. This paper develops a test approach to address this problem by computing the gaps between two consecutive type 1 elements and thereafter following the idea of "pattern" in occurrence and "directional" trend (increasing, decreasing or constant), employs the use of exact Binomial test, Kenall's Tau and Siegel-Tukey test for scale problem. Further modifications suggested by Jan Vegelius(1982) have been applied in the Siegel Tukey test to adjust for tied ranks and achieve more accurate results. This approach is distribution-free and suitable for small sizes. Also comparisons with the conventional runs test shows the superiority of the proposed approach under the null hypothesis of randomness in the occurrence of type 1 elements.
Predicting the mechanics of large structural networks, such as beam-based architected materials, requires a multiscale computational strategy that preserves information about the discrete structure while being applicable to large assemblies of struts. Especially the fracture properties of such beam lattices necessitate a two-scale modeling strategy, since the fracture toughness depends on discrete beam failure events, while the application of remote loads requires large simulation domains. As classical homogenization techniques fail in the absence of a separation of scales at the crack tip, we present a concurrent multiscale technique: a fully-nonlocal quasicontinuum (QC) multi-lattice formulation for beam networks, based on a conforming mesh. Like the original atomistic QC formulation, we maintain discrete resolution where needed (such as around a crack tip) while efficiently coarse-graining in the remaining simulation domain. A key challenge is a suitable model in the coarse-grained domain, where classical QC uses affine interpolations. This formulation fails in bending-dominated lattices, as it overconstrains the lattice by preventing bending without stretching of beams. Therefore, we here present a beam QC formulation based on mixed-order interpolation in the coarse-grained region -- combining the efficiency of linear interpolation where possible with the accuracy advantages of quadratic interpolation where needed. This results in a powerful computational framework, which, as we demonstrate through our validation and benchmark examples, overcomes the deficiencies of previous QC formulations and enables, e.g., the prediction of the fracture toughness and the diverse nature of stress distributions of stretching- and bending-dominated beam lattices in two and three dimensions.
Causal generative modelling is gaining interest in medical imaging due to its ability to answer interventional and counterfactual queries. Most work focuses on generating counterfactual images that look plausible, using auxiliary classifiers to enforce effectiveness of simulated interventions. We investigate pitfalls in this approach, discovering the issue of attribute amplification, where unrelated attributes are spuriously affected during interventions, leading to biases across protected characteristics and disease status. We show that attribute amplification is caused by the use of hard labels in the counterfactual training process and propose soft counterfactual fine-tuning to mitigate this issue. Our method substantially reduces the amplification effect while maintaining effectiveness of generated images, demonstrated on a large chest X-ray dataset. Our work makes an important advancement towards more faithful and unbiased causal modelling in medical imaging.
In many communication contexts, the capabilities of the involved actors cannot be known beforehand, whether it is a cell, a plant, an insect, or even a life form unknown to Earth. Regardless of the recipient, the message space and time scale could be too fast, too slow, too large, or too small and may never be decoded. Therefore, it pays to devise a way to encode messages agnostic of space and time scales. We propose the use of fractal functions as self-executable infinite-frequency carriers for sending messages, given their properties of structural self-similarity and scale invariance. We call it `fractal messaging'. Starting from a spatial embedding, we introduce a framework for a space-time scale-free messaging approach to this challenge. When considering a space and time-agnostic framework for message transmission, it would be interesting to encode a message such that it could be decoded at several spatio-temporal scales. Hence, the core idea of the framework proposed herein is to encode a binary message as waves along infinitely many frequencies (in power-like distributions) and amplitudes, transmit such a message, and then decode and reproduce it. To do so, the components of the Weierstrass function, a known fractal, are used as carriers of the message. Each component will have its amplitude modulated to embed the binary stream, allowing for a space-time-agnostic approach to messaging.
Distillation is the task of replacing a complicated machine learning model with a simpler model that approximates the original [BCNM06,HVD15]. Despite many practical applications, basic questions about the extent to which models can be distilled, and the runtime and amount of data needed to distill, remain largely open. To study these questions, we initiate a general theory of distillation, defining PAC-distillation in an analogous way to PAC-learning [Val84]. As applications of this theory: (1) we propose new algorithms to extract the knowledge stored in the trained weights of neural networks -- we show how to efficiently distill neural networks into succinct, explicit decision tree representations when possible by using the ``linear representation hypothesis''; and (2) we prove that distillation can be much cheaper than learning from scratch, and make progress on characterizing its complexity.
It is well known that the quasi-optimality of the Galerkin finite element method for the Helmholtz equation is dependent on the mesh size and the wave-number. In literature, different criteria have been proposed to ensure quasi-optimality. Often these criteria are difficult to obtain and depend on wave-number explicit regularity estimates. In the present work, we focus on criteria based on T-coercivity and weak T-coercivity, which highlight mesh size dependence on the gap between the square of the wavenumber and Laplace eigenvalues. We also propose an adaptive scheme, coupled with a residual-based indicator, for optimal mesh generation with minimal degrees of freedom.
Reconstructing a dynamic object with affine motion in computerized tomography (CT) leads to motion artifacts if the motion is not taken into account. In most cases, the actual motion is neither known nor can be determined easily. As a consequence, the respective model that describes CT is incomplete. The iterative RESESOP-Kaczmarz method can - under certain conditions and by exploiting the modeling error - reconstruct dynamic objects at different time points even if the exact motion is unknown. However, the method is very time-consuming. To speed the reconstruction process up and obtain better results, we combine the following three steps: 1. RESESOP-Kacmarz with only a few iterations is implemented to reconstruct the object at different time points. 2. The motion is estimated via landmark detection, e.g. using deep learning. 3. The estimated motion is integrated into the reconstruction process, allowing the use of dynamic filtered backprojection. We give a short review of all methods involved and present numerical results as a proof of principle.
Data augmentation is arguably the most important regularization technique commonly used to improve generalization performance of machine learning models. It primarily involves the application of appropriate data transformation operations to create new data samples with desired properties. Despite its effectiveness, the process is often challenging because of the time-consuming trial and error procedures for creating and testing different candidate augmentations and their hyperparameters manually. Automated data augmentation methods aim to automate the process. State-of-the-art approaches typically rely on automated machine learning (AutoML) principles. This work presents a comprehensive survey of AutoML-based data augmentation techniques. We discuss various approaches for accomplishing data augmentation with AutoML, including data manipulation, data integration and data synthesis techniques. We present extensive discussion of techniques for realizing each of the major subtasks of the data augmentation process: search space design, hyperparameter optimization and model evaluation. Finally, we carried out an extensive comparison and analysis of the performance of automated data augmentation techniques and state-of-the-art methods based on classical augmentation approaches. The results show that AutoML methods for data augmentation currently outperform state-of-the-art techniques based on conventional approaches.
Existing schemes for demonstrating quantum computational advantage are subject to various practical restrictions, including the hardness of verification and challenges in experimental implementation. Meanwhile, analog quantum simulators have been realized in many experiments to study novel physics. In this work, we propose a quantum advantage protocol based on single-step Feynman-Kitaev verification of an analog quantum simulation, in which the verifier need only run an $O(\lambda^2)$-time classical computation, and the prover need only prepare $O(1)$ samples of a history state and perform $O(\lambda^2)$ single-qubit measurements, for a security parameter $\lambda$. We also propose a near-term feasible strategy for honest provers and discuss potential experimental realizations.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191