We study the problem of lossless feature selection for a $d$-dimensional feature vector $X=(X^{(1)},\dots ,X^{(d)})$ and label $Y$ for binary classification as well as nonparametric regression. For an index set $S\subset \{1,\dots ,d\}$, consider the selected $|S|$-dimensional feature subvector $X_S=(X^{(i)}, i\in S)$. If $L^*$ and $L^*(S)$ stand for the minimum risk based on $X$ and $X_S$, respectively, then $X_S$ is called lossless if $L^*=L^*(S)$. For classification, the minimum risk is the Bayes error probability, while in regression, the minimum risk is the residual variance. We introduce nearest-neighbor based test statistics to test the hypothesis that $X_S$ is lossless. For the threshold $a_n=\log n/\sqrt{n}$, the corresponding tests are proved to be consistent under conditions on the distribution of $(X,Y)$ that are significantly milder than in previous work. Also, our threshold is dimension-independent, in contrast to earlier methods where for large $d$ the threshold becomes too large to be useful in practice.
相關內容
We study Whitney-type estimates for approximation of convex functions in the uniform norm on various convex multivariate domains while paying a particular attention to the dependence of the involved constants on the dimension and the geometry of the domain.
For a matrix $A$ which satisfies Crouzeix's conjecture, we construct several classes of matrices from $A$ for which the conjecture will also hold. We discover a new link between cyclicity and Crouzeix's conjecture, which shows that Crouzeix's Conjecture holds in full generality if and only if it holds for the differentiation operator on a class of analytic functions. We pose several open questions, which if proved, will prove Crouzeix's conjecture. We also begin an investigation into Crouzeix's conjecture for symmetric matrices and in the case of $3 \times 3$ matrices, we show Crouzeix's conjecture holds for symmetric matrices if and only if it holds for analytic truncated Toeplitz operators.
We prove the following variant of Levi's Enlargement Lemma: for an arbitrary arrangement $\mathcal{A}$ of $x$-monotone pseudosegments in the plane and a pair of points $a,b$ with distinct $x$-coordinates and not on the same pseudosegment, there exists a simple $x$-monotone curve with endpoints $a,b$ that intersects every curve of $\mathcal{A}$ at most once. As a consequence, every simple monotone drawing of a graph can be extended to a simple monotone drawing of a complete graph. We also show that extending an arrangement of cylindrically monotone pseudosegments is not always possible; in fact, the corresponding decision problem is NP-hard.
The Davis-Kahan-Wedin $\sin \Theta$ theorem describes how the singular subspaces of a matrix change when subjected to a small perturbation. This classic result is sharp in the worst case scenario. In this paper, we prove a stochastic version of the Davis-Kahan-Wedin $\sin \Theta$ theorem when the perturbation is a Gaussian random matrix. Under certain structural assumptions, we obtain an optimal bound that significantly improves upon the classic Davis-Kahan-Wedin $\sin \Theta$ theorem. One of our key tools is a new perturbation bound for the singular values, which may be of independent interest.
In this short note, we present a refined approximation for the log-ratio of the density of the von Mises$(\mu,\kappa)$ distribution (also called the circular normal distribution) to the standard (linear) normal distribution when the concentration parameter \k{appa} is large. Our work complements the one of Hill (1976), who obtained a very similar approximation along with quantile couplings, using earlier approximations by Hill & Davis (1968) of Cornish-Fisher type. One motivation for this note is to highlight the connection between the circular and linear normal distributions through their circular variance and (linear) variance.
We incorporate strong negation in the theory of computable functionals TCF, a common extension of Plotkin's PCF and G\"{o}del's system $\mathbf{T}$, by defining simultaneously strong negation $A^{\mathbf{N}}$ of a formula $A$ and strong negation $P^{\mathbf{N}}$ of a predicate $P$ in TCF. As a special case of the latter, we get strong negation of an inductive and a coinductive predicate of TCF. We prove appropriate versions of the Ex falso quodlibet and of double negation elimination for strong negation in TCF. We introduce the so-called tight formulas of TCF i.e., formulas implied from the weak negation of their strong negation, and the relative tight formulas. We present various case-studies and examples, which reveal the naturality of our definition of strong negation in TCF and justify the use of TCF as a formal system for a large part of Bishop-style constructive mathematics.
The Allen-Cahn equation (ACE) inherently possesses two crucial properties: the maximum principle and the energy dissipation law. Preserving these two properties at the discrete level is also necessary in the numerical methods for the ACE. In this paper, unlike the traditional top-down macroscopic numerical schemes which discretize the ACE directly, we first propose a novel bottom-up mesoscopic regularized lattice Boltzmann method based macroscopic numerical scheme for d(=1,2,3)-dimensional ACE, where the DdQ(2d+1) [(2d+1) discrete velocities in d-dimensional space] lattice structure is adopted. In particular, the proposed macroscopic numerical scheme has a second-order accuracy in space, and can also be viewd as an implicit-explicit finite-difference scheme for the ACE, in which the nonlinear term is discretized semi-implicitly, the temporal derivative and dissipation term of the ACE are discretized by using the explicit Euler method and second-order central difference method, respectively. Then we also demonstrate that the proposed scheme can preserve the maximum bound principle and the original energy dissipation law at the discrete level under some conditions. Finally, some numerical experiments are conducted to validate our theoretical analysis.
We define the notion of $k$-safe infinitary series over idempotent ordered totally generalized product $\omega $-valuation monoids that satisfy specific properties. For each element $k$ of the underlying structure (different from the neutral elements of the additive, and the multiplicative operation) we determine two syntactic fragments of the weighted $LTL$ with the property that the semantics of the formulas in these fragments are $k$ -safe infinitary series. For specific idempotent ordered totally generalized product $\omega $-valuation monoids we provide algorithms that given a weighted B\"{u}chi automaton and a weighted $LTL$ formula in these fragments, decide whether the behavior of the automaton coincides with the semantics of the formula.
We show that the set of $m \times m$ complex skew-symmetric matrix polynomials of even grade $d$, i.e., of degree at most $d$, and (normal) rank at most $2r$ is the closure of the single set of matrix polynomials with certain, explicitly described, complete eigenstructure. This complete eigenstructure corresponds to the most generic $m \times m$ complex skew-symmetric matrix polynomials of even grade $d$ and rank at most $2r$. The analogous problem for the case of skew-symmetric matrix polynomials of odd grade is solved in [Linear Algebra Appl., 536:1-18, 2018].
Fractional calculus with respect to function $\psi$, also named as $\psi$-fractional calculus, generalizes the Hadamard and the Riemann-Liouville fractional calculi, which causes challenge in numerical treatment. In this paper we study spectral-type methods using mapped Jacobi functions (MJFs) as basis functions and obtain efficient algorithms to solve $\psi$-fractional differential equations. In particular, we setup the Petrov-Galerkin spectral method and spectral collocation method for initial and boundary value problems involving $\psi$-fractional derivatives. We develop basic approximation theory for the MJFs and conduct the error estimates of the derived methods. We also establish a recurrence relation to evaluate the collocation differentiation matrix for implementing the spectral collocation algorithm. Numerical examples confirm the theoretical results and demonstrate the effectiveness of the spectral and collocation methods.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191