The recently-emerging field of higher order MDS codes has sought to unify a number of concepts in coding theory. Such areas captured by higher order MDS codes include maximally recoverable (MR) tensor codes, codes with optimal list-decoding guarantees, and codes with constrained generator matrices (as in the GM-MDS theorem). By proving these equivalences, Brakensiek-Gopi-Makam showed the existence of optimally list-decodable Reed-Solomon codes over exponential sized fields. Building on this, recent breakthroughs by Guo-Zhang and Alrabiah-Guruswami-Li have shown that randomly punctured Reed-Solomon codes achieve list-decoding capacity (which is a relaxation of optimal list-decodability) over linear size fields. We extend these works by developing a formal theory of relaxed higher order MDS codes. In particular, we show that there are two inequivalent relaxations which we call lower and upper relaxations. The lower relaxation is equivalent to relaxed optimal list-decodable codes and the upper relaxation is equivalent to relaxed MR tensor codes with a single parity check per column. We then generalize the techniques of GZ and AGL to show that both these relaxations can be constructed over constant size fields by randomly puncturing suitable algebraic-geometric codes. For this, we crucially use the generalized GM-MDS theorem for polynomial codes recently proved by Brakensiek-Dhar-Gopi. We obtain the following corollaries from our main result. First, randomly punctured AG codes of rate $R$ achieve list-decoding capacity with list size $O(1/\epsilon)$ and field size $\exp(O(1/\epsilon^2))$. Prior to this work, AG codes were not even known to achieve list-decoding capacity. Second, by randomly puncturing AG codes, we can construct relaxed MR tensor codes with a single parity check per column over constant-sized fields, whereas (non-relaxed) MR tensor codes require exponential field size.
相關內容
Probabilistic variants of Model Order Reduction (MOR) methods have recently emerged for improving stability and computational performance of classical approaches. In this paper, we propose a probabilistic Reduced Basis Method (RBM) for the approximation of a family of parameter-dependent functions. It relies on a probabilistic greedy algorithm with an error indicator that can be written as an expectation of some parameter-dependent random variable. Practical algorithms relying on Monte Carlo estimates of this error indicator are discussed. In particular, when using Probably Approximately Correct (PAC) bandit algorithm, the resulting procedure is proven to be a weak greedy algorithm with high probability. Intended applications concern the approximation of a parameter-dependent family of functions for which we only have access to (noisy) pointwise evaluations. As a particular application, we consider the approximation of solution manifolds of linear parameter-dependent partial differential equations with a probabilistic interpretation through the Feynman-Kac formula.
We provide numerical bounds on the Crouzeix ratiofor KLS matrices $A$ which have a line segment on the boundary of the numerical range. The Crouzeix ratio is the supremum over all polynomials $p$ of the spectral norm of $p(A)$ dividedby the maximum absolute value of $p$ on the numerical range of $A$.Our bounds confirm the conjecture that this ratiois less than or equal to $2$. We also give a precise description of these numerical ranges.
Longitudinal studies are often subject to missing data. The ICH E9(R1) addendum addresses the importance of defining a treatment effect estimand with the consideration of intercurrent events. Jump-to-reference (J2R) is one classically envisioned control-based scenario for the treatment effect evaluation using the hypothetical strategy, where the participants in the treatment group after intercurrent events are assumed to have the same disease progress as those with identical covariates in the control group. We establish new estimators to assess the average treatment effect based on a proposed potential outcomes framework under J2R. Various identification formulas are constructed under the assumptions addressed by J2R, motivating estimators that rely on different parts of the observed data distribution. Moreover, we obtain a novel estimator inspired by the efficient influence function, with multiple robustness in the sense that it achieves $n^{1/2}$-consistency if any pairs of multiple nuisance functions are correctly specified, or if the nuisance functions converge at a rate not slower than $n^{-1/4}$ when using flexible modeling approaches. The finite-sample performance of the proposed estimators is validated in simulation studies and an antidepressant clinical trial.
This paper considers a crowdsourced delivery (CSD) system that effectively utilizes the existing trips to fulfill parcel delivery as a matching problem between CSD drivers and delivery tasks. This matching problem has two major challenges. First, it is a large-scale combinatorial optimization problem that is hard to solve in a reasonable computational time. Second, the evaluation of the objective function for socially optimal matching contains the utility of drivers for performing the tasks, which is generally unobservable private information. To address these challenges, this paper proposes a hierarchical distribution mechanism of CSD tasks that decomposes the matching problem into the task partition (master problem) and individual task-driver matching within smaller groups of drivers (sub-problems). We incorporate an auction mechanism with truth-telling and efficiency into the sub-problems so that the drivers' perceived utilities are revealed through their bids. Furthermore, we formulate the master problem as a fluid model based on continuously approximated decision variables. By exploiting the random utility framework, we analytically represent the objective function of the problem using continuous variables, without explicitly knowing the drivers' utilities. The numerical experiment shows that the proposed approach solved large-scale matching problems at least 100 times faster than a naive LP solver and approximated the original objective value with errors of less than 1%.
We establish that a large and flexible class of long, high redundancy error correcting codes can be efficiently and accurately decoded with guessing random additive noise decoding (GRAND). Performance evaluation demonstrates that it is possible to construct simple concatenated codes that outperform low-density parity-check (LDPC) codes found in the 5G New Radio standard. The concatenated structure enables many desirable features, including: low-complexity hardware-friendly encoding and decoding; high levels of flexibility in length and rate through modularity; and high levels of parallelism in encoding and decoding that enable low latency. Central to this is the development of a method through which any soft-input (SI) GRAND algorithm can provide soft-output (SO) in the form of an accurate a-posteriori estimate of the likelihood that a decoding is correct or, in the case of list decoding, the likelihood that each element of the list is correct. The key distinguishing feature of SOGRAND in comparison to other methods is the provision of an estimate that the correct decoding has not been found, even when providing a single decoding. That per-block SO can be converted into accurate per-bit SO by a weighted sum that includes a term for the SI. Crucially, implementing SOGRAND adds negligible computation and memory to the existing decoding process, and using it results in a practical alternative to LDPC codes.
The Cox proportional hazards model (Cox model) is a popular model for survival data analysis. When the sample size is small relative to the dimension of the model, the standard maximum partial likelihood inference is often problematic. In this work, we propose the Cox catalytic prior distributions for Bayesian inference on Cox models, which is an extension of a general class of prior distributions originally designed for stabilizing complex parametric models. The Cox catalytic prior is formulated as a weighted likelihood of the regression coefficients based on synthetic data and a surrogate baseline hazard constant. This surrogate hazard can be either provided by the user or estimated from the data, and the synthetic data are generated from the predictive distribution of a fitted simpler model. For point estimation, we derive an approximation of the marginal posterior mode, which can be computed conveniently as a regularized log partial likelihood estimator. We prove that our prior distribution is proper and the resulting estimator is consistent under mild conditions. In simulation studies, our proposed method outperforms standard maximum partial likelihood inference and is on par with existing shrinkage methods. We further illustrate the application of our method to a real dataset.
We propose a geometric integrator to numerically approximate the flow of Lie systems. The key is a novel procedure that integrates the Lie system on a Lie group intrinsically associated with a Lie system on a general manifold via a Lie group action, and then generates the discrete solution of the Lie system on the manifold via a solution of the Lie system on the Lie group. One major result from the integration of a Lie system on a Lie group is that one is able to solve all associated Lie systems on manifolds at the same time, and that Lie systems on Lie groups can be described through first-order systems of linear homogeneous ordinary differential equations (ODEs) in normal form. This brings a lot of advantages, since solving a linear system of ODEs involves less numerical cost. Specifically, we use two families of numerical schemes on the Lie group, which are designed to preserve its geometrical structure: the first one based on the Magnus expansion, whereas the second is based on Runge-Kutta-Munthe-Kaas (RKMK) methods. Moreover, since the aforementioned action relates the Lie group and the manifold where the Lie system evolves, the resulting integrator preserves any geometric structure of the latter. We compare both methods for Lie systems with geometric invariants, particularly a class on Lie systems on curved spaces. We also illustrate the superiority of our method for describing long-term behavior and for differential equations admitting solutions whose geometric features depends heavily on initial conditions. As already mentioned, our milestone is to show that the method we propose preserves all the geometric invariants very faithfully, in comparison with nongeometric numerical methods.
We extend a localization result for the $H^{1/2}$ norm by B. Faermann to a wider class of subspaces of $H^{1/2}(\Gamma)$, and we prove an analogous result for the $H^{-1/2}(\Gamma)$ norm, $\Gamma$ being the boundary of a bounded polytopal domain $\Omega$ in $\mathbb{R}^n$, $n=2,3$. As a corollary, we obtain equivalent, better localized, norms for both $H^{1/2}(\Gamma)$ and $H^{-1/2}(\Gamma)$, which can be exploited, for instance, in the design of preconditioners or of stabilized methods.
Fitness functions map large combinatorial spaces of biological sequences to properties of interest. Inferring these multimodal functions from experimental data is a central task in modern protein engineering. Global epistasis models are an effective and physically-grounded class of models for estimating fitness functions from observed data. These models assume that a sparse latent function is transformed by a monotonic nonlinearity to emit measurable fitness. Here we demonstrate that minimizing contrastive loss functions, such as the Bradley-Terry loss, is a simple and flexible technique for extracting the sparse latent function implied by global epistasis. We argue by way of a fitness-epistasis uncertainty principle that the nonlinearities in global epistasis models can produce observed fitness functions that do not admit sparse representations, and thus may be inefficient to learn from observations when using a Mean Squared Error (MSE) loss (a common practice). We show that contrastive losses are able to accurately estimate a ranking function from limited data even in regimes where MSE is ineffective. We validate the practical utility of this insight by showing contrastive loss functions result in consistently improved performance on benchmark tasks.
The present article proposes a partitioned Dirichlet-Neumann algorithm, that allows to address unique challenges arising from a novel mixed-dimensional coupling of very slender fibers embedded in fluid flow using a regularized mortar-type finite element discretization. The fibers are modeled via one-dimensional (1D) partial differential equations based on geometrically exact nonlinear beam theory, while the flow is described by the three-dimensional (3D) incompressible Navier-Stokes equations. The arising truly mixed-dimensional 1D-3D coupling scheme constitutes a novel approximate model and numerical strategy, that naturally necessitates specifically tailored solution schemes to ensure an accurate and efficient computational treatment. In particular, we present a strongly coupled partitioned solution algorithm based on a Quasi-Newton method for applications involving fibers with high slenderness ratios that usually present a challenge with regard to the well-known added mass effect. The influence of all employed algorithmic and numerical parameters, namely the applied acceleration technique, the employed constraint regularization parameter as well as shape functions, on efficiency and results of the solution procedure is studied through appropriate examples. Finally, the convergence of the two-way coupled mixed-dimensional problem solution under uniform mesh refinement is demonstrated, a comparison to a 3D reference solution is performed, and the method's capabilities in capturing flow phenomena at large geometric scale separation is illustrated by the example of a submersed vegetation canopy.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191