In this paper, we study the problem of recovering a ground truth high dimensional piecewise linear curve $C^*(t):[0, 1]\to\mathbb{R}^d$ from a high noise Gaussian point cloud with covariance $\sigma^2I$ centered around the curve. We establish that the sample complexity of recovering $C^*$ from data scales with order at least $\sigma^6$. We then show that recovery of a piecewise linear curve from the third moment is locally well-posed, and hence $O(\sigma^6)$ samples is also sufficient for recovery. We propose methods to recover a curve from data based on a fitting to the third moment tensor with a careful initialization strategy and conduct some numerical experiments verifying the ability of our methods to recover curves. All code for our numerical experiments is publicly available on GitHub.
相關內容
Martin-L\"{o}f type theory $\mathbf{MLTT}$ was extended by Setzer with the so-called Mahlo universe types. The extension of $\mathbf{MLTT}$ with one Mahlo universe is called $\mathbf{MLM}$ and was introduced to develop a variant of $\mathbf{MLTT}$ equipped with an analogue of a large cardinal. Another instance of constructive systems extended with an analogue of a large set was formulated in the context of Aczel's constructive set theory: $\mathbf{CZF}$. Rathjen, Griffor and Palmgren extended $\mathbf{CZF}$ with inaccessible sets of all transfinite orders. While Rathjen proved that this extended system of $\mathbf{CZF}$ is interpretable in an extension of $\mathbf{MLM}$ with one usual universe type above the Mahlo universe, it is unknown whether it can be interpreted by the Mahlo universe without a universe type above it. We extend $\mathbf{MLM}$ not by a universe type but by the accessibility predicate, and show that $\mathbf{CZF}$ with inaccessible sets can be interpreted in $\mathbf{MLM}$ with the accessibility predicate. Our interpretation of this extension of $\mathbf{CZF}$ is the same as that of Rathjen, Griffor and Palmgren formulated by $\mathbf{MLTT}$ with second-order universe operators, except that we construct the inaccessible sets by using the Mahlo universe and the accessibility predicate. We formalised the main part of our interpretation in the proof assistant Agda.
It is known that the set of lumpable Markov chains over a finite state space, with respect to a fixed lumping function, generally does not form an exponential family of stochastic matrices. In this work, we explore efficiently verifiable necessary and sufficient combinatorial conditions for families of lumpable transition matrices to form exponential families.
Given a point set $P$ in a metric space and a real number $t \geq 1$, an \emph{oriented $t$-spanner} is an oriented graph $\overrightarrow{G}=(P,\overrightarrow{E})$, where for every pair of distinct points $p$ and $q$ in $P$, the shortest oriented closed walk in $\overrightarrow{G}$ that contains $p$ and $q$ is at most a factor $t$ longer than the perimeter of the smallest triangle in $P$ containing $p$ and $q$. The \emph{oriented dilation} of a graph $\overrightarrow{G}$ is the minimum $t$ for which $\overrightarrow{G}$ is an oriented $t$-spanner. We present the first algorithm that computes, in Euclidean space, a sparse oriented spanner whose oriented dilation is bounded by a constant. More specifically, for any set of $n$ points in $\mathbb{R}^d$, where $d$ is a constant, we construct an oriented $(2+\varepsilon)$-spanner with $\mathcal{O}(n)$ edges in $\mathcal{O}(n \log n)$ time and $\mathcal{O}(n)$ space. Our construction uses the well-separated pair decomposition and an algorithm that computes a $(1+\varepsilon)$-approximation of the minimum-perimeter triangle in $P$ containing two given query points in $\mathcal{O}(\log n)$ time. While our algorithm is based on first computing a suitable undirected graph and then orienting it, we show that, in general, computing the orientation of an undirected graph that minimises its oriented dilation is NP-hard, even for point sets in the Euclidean plane. We further prove that even if the orientation is already given, computing the oriented dilation is APSP-hard for points in a general metric space. We complement this result with an algorithm that approximates the oriented dilation of a given graph in subcubic time for point sets in $\mathbb{R}^d$, where $d$ is a constant.
The ideal estimand for comparing a new treatment $Rx$ with a control $C$ is the $\textit{counterfactual}$ efficacy $Rx:C$, the expected differential outcome between $Rx$ and $C$ if each patient were given $\textit{both}$. While counterfactual $\textit{point estimation}$ from $\textit{factual}$ Randomized Controlled Trials (RCTs) has been available, this article shows $\textit{counterfactual}$ uncertainty quantification (CUQ), quantifying uncertainty for factual point estimates but in a counterfactual setting, is surprisingly achievable. We achieve CUQ whose variability is typically smaller than factual UQ, by creating a new statistical modeling principle called ETZ which is applicable to RCTs with $\textit{Before-and-After}$ treatment Repeated Measures, common in many therapeutic areas. We urge caution when estimate of the unobservable true condition of a patient before treatment has measurement error, because that violation of standard regression assumption can cause attenuation in estimating treatment effects. Fortunately, we prove that, for traditional medicine in general, and for targeted therapy with efficacy defined as averaged over the population, counterfactual point estimation is unbiased. However, for targeted therapy, both Real Human and Digital Twins approaches should respect this limitation, lest predicted treatment effect in $\textit{subgroups}$ will have bias.
The problem of substructure characteristic modes is developed using a scattering matrix-based formulation, generalizing subregion characteristic mode decomposition to arbitrary computational tools. It is shown that the modes of the scattering formulation are identical to the modes of the classical formulation based on the background Green's function for lossless systems under conditions where both formulations can be applied. The scattering formulation, however, opens a variety of new subregion scenarios unavailable within previous formulations, including cases with lumped or wave ports or subregions in circuits. Thanks to its scattering nature, the formulation is solver-agnostic with the possibility to utilize an arbitrary full-wave method.
HyperQPTL and HyperQPTL$^+$ are expressive specification languages for hyperproperties, i.e., properties that relate multiple executions of a system. Tight complexity bounds are known for HyperQPTL finite-state satisfiability and model-checking. Here, we settle the complexity of satisfiability for HyperQPTL as well as satisfiability, finite-state satisfiability, and model-checking for HyperQPTL$^+$: the former is equivalent to truth in second-order arithmetic, the latter are all equivalent to truth in third-order arithmetic, i.e., they are all four very undecidable.
Let $\Gamma$ be a function that maps two arbitrary graphs $G$ and $H$ to a non-negative real number such that $$\alpha(G^{\boxtimes n})\leq \alpha(H^{\boxtimes n})\Gamma(G,H)^n$$ where $n$ is any natural number and $G^{\boxtimes n}$ is the strong product of $G$ with itself $n$ times. We establish the equivalence of two different approaches for finding such a function $\Gamma$. The common solution obtained through either approach is termed ``the relative fractional independence number of a graph $G$ with respect to another graph $H$". We show this function by $\alpha^*(G|H)$ and discuss some of its properties. In particular, we show that $\alpha^*(G|H)\geq \frac{X(G)}{X(H)} \geq \frac{1}{\alpha^*(H|G)},$ where $X(G)$ can be the independence number, the Shannon capacity, the fractional independence number, the Lov\'{a}sz number, or the Schrijver's or Szegedy's variants of the Lov\'{a}sz number of a graph $G$. This inequality is the first explicit non-trivial upper bound on the ratio of the invariants of two arbitrary graphs, as mentioned earlier, which can also be used to obtain upper or lower bounds for these invariants. As explicit applications, we present new upper bounds for the ratio of the Shannon capacity of two Cayley graphs and compute new lower bounds on the Shannon capacity of certain Johnson graphs (yielding the exact value of their Haemers number). Moreover, we show that $\alpha^*(G|H)$ can be used to present a stronger version of the well-known No-Homomorphism Lemma.
The hypergraph Zarankiewicz's problem, introduced by Erd\H{o}s in 1964, asks for the maximum number of hyperedges in an $r$-partite hypergraph with $n$ vertices in each part that does not contain a copy of $K_{t,t,\ldots,t}$. Erd\H{o}s obtained a near optimal bound of $O(n^{r-1/t^{r-1}})$ for general hypergraphs. In recent years, several works obtained improved bounds under various algebraic assumptions -- e.g., if the hypergraph is semialgebraic. In this paper we study the problem in a geometric setting -- for $r$-partite intersection hypergraphs of families of geometric objects. Our main results are essentially sharp bounds for families of axis-parallel boxes in $\mathbb{R}^d$ and families of pseudo-discs. For axis-parallel boxes, we obtain the sharp bound $O_{d,t}(n^{r-1}(\frac{\log n}{\log \log n})^{d-1})$. The best previous bound was larger by a factor of about $(\log n)^{d(2^{r-1}-2)}$. For pseudo-discs, we obtain the bound $O_t(n^{r-1}(\log n)^{r-2})$, which is sharp up to logarithmic factors. As this hypergraph has no algebraic structure, no improvement of Erd\H{o}s' 60-year-old $O(n^{r-1/t^{r-1}})$ bound was known for this setting. Futhermore, even in the special case of discs for which the semialgebraic structure can be used, our result improves the best known result by a factor of $\tilde{\Omega}(n^{\frac{2r-2}{3r-2}})$. To obtain our results, we use the recently improved results for the graph Zarankiewicz's problem in the corresponding settings, along with a variety of combinatorial and geometric techniques, including shallow cuttings, biclique covers, transversals, and planarity.
In this paper, we analyze the computational limitations of Mamba and State-space Models (SSMs) by using the circuit complexity framework. Despite Mamba's stateful design and recent attention as a strong candidate to outperform Transformers, we have demonstrated that both Mamba and SSMs with $\mathrm{poly}(n)$-precision and constant-depth layers reside within the $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^0$ complexity class. This result indicates Mamba has the same computational capabilities as Transformer theoretically, and it cannot solve problems like arithmetic formula problems, boolean formula value problems, and permutation composition problems if $\mathsf{TC}^0 \neq \mathsf{NC}^1$. Therefore, it challenges the assumption Mamba is more computationally expressive than Transformers. Our contributions include rigorous proofs showing that Selective SSM and Mamba architectures can be simulated by $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^0$ circuits, and they cannot solve problems outside $\mathsf{TC}^0$.
In this paper, we describe an algorithm for approximating functions of the form $f(x)=\int_{a}^{b} x^{\mu} \sigma(\mu) \, d \mu$ over $[0,1]$, where $\sigma(\mu)$ is some signed Radon measure, or, more generally, of the form $f(x) = <\sigma(\mu),\, x^\mu>$, where $\sigma(\mu)$ is some distribution supported on $[a,b]$, with $0 <a < b < \infty$. One example from this class of functions is $x^c (\log{x})^m=(-1)^m <\delta^{(m)}(\mu-c), \, x^\mu>$, where $a\leq c \leq b$ and $m \geq 0$ is an integer. Given the desired accuracy $\epsilon$ and the values of $a$ and $b$, our method determines a priori a collection of non-integer powers $t_1$, $t_2$, $\ldots$, $t_N$, so that the functions are approximated by series of the form $f(x)\approx \sum_{j=1}^N c_j x^{t_j}$, and a set of collocation points $x_1$, $x_2$, $\ldots$, $x_N$, such that the expansion coefficients can be found by collocating the function at these points. We prove that our method has a small uniform approximation error which is proportional to $\epsilon$ multiplied by some small constants, and that the number of singular powers and collocation points grows as $N=O(\log{\frac{1}{\epsilon}})$. We demonstrate the performance of our algorithm with several numerical experiments.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191