Convolutional codes with a maximum distance profile attain the largest possible column distances for the maximum number of time instants and thus have outstanding error-correcting capability especially for streaming applications. Explicit constructions of such codes are scarce in the literature. In particular, known constructions of convolutional codes with rate k/n and a maximum distance profile require a field of size at least exponential in n for general code parameters. At the same time, the only known lower bound on the field size is the trivial bound that is linear in n. In this paper, we show that a finite field of size $\Omega_L(n^{L-1})$ is necessary for constructing convolutional codes with rate k/n and a maximum distance profile of length L. As a direct consequence, this rules out the possibility of constructing convolutional codes with a maximum distance profile of length L >= 3 over a finite field of size O(n). Additionally, we also present an explicit construction of convolutional code with rate k/n and a maximum profile of length L = 1 over a finite field of size $O(n^{\min\{k,n-k\}})$, achieving a smaller field size than known constructions with the same profile length.
相關內容
Automated decision support systems promise to help human experts solve multiclass classification tasks more efficiently and accurately. However, existing systems typically require experts to understand when to cede agency to the system or when to exercise their own agency. Otherwise, the experts may be better off solving the classification tasks on their own. In this work, we develop an automated decision support system that, by design, does not require experts to understand when to trust the system to improve performance. Rather than providing (single) label predictions and letting experts decide when to trust these predictions, our system provides sets of label predictions constructed using conformal prediction$\unicode{x2014}$prediction sets$\unicode{x2014}$and forcefully asks experts to predict labels from these sets. By using conformal prediction, our system can precisely trade-off the probability that the true label is not in the prediction set, which determines how frequently our system will mislead the experts, and the size of the prediction set, which determines the difficulty of the classification task the experts need to solve using our system. In addition, we develop an efficient and near-optimal search method to find the conformal predictor under which the experts benefit the most from using our system. Simulation experiments using synthetic and real expert predictions demonstrate that our system may help experts make more accurate predictions and is robust to the accuracy of the classifier the conformal predictor relies on.
Wasserstein gradient flows on probability measures have found a host of applications in various optimization problems. They typically arise as the continuum limit of exchangeable particle systems evolving by some mean-field interaction involving a gradient-type potential. However, in many problems, such as in multi-layer neural networks, the so-called particles are edge weights on large graphs whose nodes are exchangeable. Such large graphs are known to converge to continuum limits called graphons as their size grow to infinity. We show that the Euclidean gradient flow of a suitable function of the edge-weights converges to a novel continuum limit given by a curve on the space of graphons that can be appropriately described as a gradient flow or, more technically, a curve of maximal slope. Several natural functions on graphons, such as homomorphism functions and the scalar entropy, are covered by our set-up, and the examples have been worked out in detail.
This work proposes a discretization of the acoustic wave equation with possibly oscillatory coefficients based on a superposition of discrete solutions to spatially localized subproblems computed with an implicit time discretization. Based on exponentially decaying entries of the global system matrices and an appropriate partition of unity, it is proved that the superposition of localized solutions is appropriately close to the solution of the (global) implicit scheme. It is thereby justified that the localized (and especially parallel) computation on multiple overlapping subdomains is reasonable. Moreover, a re-start is introduced after a certain amount of time steps to maintain a moderate overlap of the subdomains. Overall, the approach may be understood as a domain decomposition strategy (in space and time) that completely avoids inner iterations. Numerical examples are presented.
Ferrers diagram rank-metric codes were introduced by Etzion and Silberstein in 2009. In their work, they proposed a conjecture on the largest dimension of a space of matrices over a finite field whose nonzero elements are supported on a given Ferrers diagram and all have rank lower bounded by a fixed positive integer $d$. Since stated, the Etzion-Silberstein conjecture has been verified in a number of cases, often requiring additional constraints on the field size or on the minimum rank $d$ in dependence of the corresponding Ferrers diagram. As of today, this conjecture still remains widely open. Using modular methods, we give a constructive proof of the Etzion-Silberstein conjecture for the class of strictly monotone Ferrers diagrams, which does not depend on the minimum rank $d$ and holds over every finite field. In addition, we leverage on the last result to also prove the conjecture for the class of MDS-constructible Ferrers diagrams, without requiring any restriction on the field size.
We derive both Azuma-Hoeffding and Burkholder-type inequalities for partial sums over a rectangular grid of dimension $d$ of a random field satisfying a weak dependency assumption of projective type: the difference between the expectation of an element of the random field and its conditional expectation given the rest of the field at a distance more than $\delta$ is bounded, in $L^p$ distance, by a known decreasing function of $\delta$. The analysis is based on the combination of a multi-scale approximation of random sums by martingale difference sequences, and of a careful decomposition of the domain. The obtained results extend previously known bounds under comparable hypotheses, and do not use the assumption of commuting filtrations.
The problem of finding the connected components of a graph is considered. The algorithms addressed to solve the problem are used to solve such problems on graphs as problems of finding points of articulation, bridges, maximin bridge, etc. A natural approach to solving this problem is a breadth-first search, the implementations of which are presented in software libraries designed to maximize the use of the capabi\-lities of modern computer architectures. We present an approach using perturbations of adjacency matrix of a graph. We check wether the graph is connected or not by comparing the solutions of the two systems of linear algebraic equations (SLAE): the first SLAE with a perturbed adjacency matrix of the graph and the second SLAE with~unperturbed matrix. This approach makes it possible to use effective numerical implementations of SLAE solution methods to solve connectivity problems on graphs. Iterations of iterative numerical methods for solving such SLAE can be considered as carrying out a graph traversal. Generally speaking, the traversal is not equivalent to the traversal that is carried out with breadth-first search. An algorithm for finding the connected components of a graph using such a traversal is presented. For any instance of the problem, this algorithm has no greater computational complexity than breadth-first search, and for~most individual problems it has less complexity.
We propose a sampling algorithm that achieves superior complexity bounds in all the classical settings (strongly log-concave, log-concave, Logarithmic-Sobolev inequality (LSI), Poincar\'e inequality) as well as more general settings with semi-smooth or composite potentials. Our algorithm is based on the proximal sampler introduced in~\citet{lee2021structured}. The performance of this proximal sampler is determined by that of the restricted Gaussian oracle (RGO), a key step in the proximal sampler. The main contribution of this work is an inexact realization of RGO based on approximate rejection sampling. To bound the inexactness of RGO, we establish a new concentration inequality for semi-smooth functions over Gaussian distributions, extending the well-known concentration inequality for Lipschitz functions. Applying our RGO implementation to the proximal sampler, we achieve state-of-the-art complexity bounds in almost all settings. For instance, for strongly log-concave distributions, our method has complexity bound $\tilde\mathcal{O}(\kappa d^{1/2})$ without warm start, better than the minimax bound for MALA. For distributions satisfying the LSI, our bound is $\tilde \mathcal{O}(\hat \kappa d^{1/2})$ where $\hat \kappa$ is the ratio between smoothness and the LSI constant, better than all existing bounds.
We derive upper bounds on the Wasserstein distance ($W_1$), with respect to $\sup$-norm, between any continuous $\mathbb{R}^d$ valued random field indexed by the $n$-sphere and the Gaussian, based on Stein's method. We develop a novel Gaussian smoothing technique that allows us to transfer a bound in a smoother metric to the $W_1$ distance. The smoothing is based on covariance functions constructed using powers of Laplacian operators, designed so that the associated Gaussian process has a tractable Cameron-Martin or Reproducing Kernel Hilbert Space. This feature enables us to move beyond one dimensional interval-based index sets that were previously considered in the literature. Specializing our general result, we obtain the first bounds on the Gaussian random field approximation of wide random neural networks of any depth and Lipschitz activation functions at the random field level. Our bounds are explicitly expressed in terms of the widths of the network and moments of the random weights. We also obtain tighter bounds when the activation function has three bounded derivatives.
In the classic implementation of the LOBPCG method, orthogonalization and the R-R (Rayleigh-Ritz) procedure cost nonignorable CPU time. Especially this consumption could be very expensive to deal with situations with large block sizes. In this paper, we propose an orthogonalization-free framework of implementing the LOBPCG method for SCF (self-consistent field) iterations in solving the Kohn-Sham equation. In this framework, orthogonalization is avoided in calculations, which can decrease the computational complexity. And the R-R procedure is implemented parallelly through OpenMP, which can further reduce computational time. During numerical experiments, an effective preconditioning strategy is designed, which can accelerate the LOBPCG method remarkably. Consequently, the efficiency of the LOBPCG method can be significantly improved. Based on this, the SCF iteration can solve the Kohn-Sham equation efficiently. A series of numerical experiments are inducted to demonstrate the effectiveness of our implementation, in which significant improvements in computational time can be observed.
In this paper, we are concerned with efficiently solving the sequences of regularized linear least squares problems associated with employing Tikhonov-type regularization with regularization operators designed to enforce edge recovery. An optimal regularization parameter, which balances the fidelity to the data with the edge-enforcing constraint term, is typically not known a priori. This adds to the total number of regularized linear least squares problems that must be solved before the final image can be recovered. Therefore, in this paper, we determine effective multigrid preconditioners for these sequences of systems. We focus our approach on the sequences that arise as a result of the edge-preserving method introduced in [6], where we can exploit an interpretation of the regularization term as a diffusion operator; however, our methods are also applicable in other edge-preserving settings, such as iteratively reweighted least squares problems. Particular attention is paid to the selection of components of the multigrid preconditioner in order to achieve robustness for different ranges of the regularization parameter value. In addition, we present a parameter culling approach that, when used with the L-curve heuristic, reduces the total number of solves required. We demonstrate our preconditioning and parameter culling routines on examples in computed tomography and image deblurring.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191