Group testing is a technique which avoids individually testing $n$ samples for a rare disease and instead tests $n < p$ pools, where a pool consists of a mixture of small, equal portions of a subset of the $p$ samples. Group testing saves testing time and resources in many applications, including RT-PCR, with guarantees for the recovery of the status of the $p$ samples from results on $n$ pools. The noise in quantitative RT- PCR is inherently known to follow a multiplicative data-dependent model. In recent literature, the corresponding linear systems for inferring the health status of $p$ samples from results on $n$ pools have been solved using the Lasso estimator and its variants, which have been typically used in additive Gaussian noise settings. There is no existing literature which establishes performance bounds for Lasso for the multiplicative noise model associated with RT-PCR. After noting that a recent general technique, Hunt et al., works for Poisson inverse problems, we adapt it to handle sparse signal reconstruction from compressive measurements with multiplicative noise: we present high probability performance bounds and data-dependent weights for the Lasso and its weighted version. We also show numerical results on simulated pooled RT-PCR data to empirically validate our bounds.
相關內容
Karppa & Kaski (2019) proposed a novel type of ``broken" or ``opportunistic" multiplication algorithm, based on a variant of Strassen's algorithm, and used this to develop new algorithms for Boolean matrix multiplication, among other tasks. For instance, their algorithm can compute Boolean matrix multiplication in $O(n^{\log_2(6+6/7)} \log n) = O(n^{2.778})$ time. While faster matrix multiplication algorithms exist asymptotically, in practice most such algorithms are infeasible for practical problems. In this note, we describe an alternate way to use the broken matrix multiplication algorithm to approximately compute matrix multiplication, either for real-valued matrices or Boolean matrices. In brief, instead of running multiple iterations of the broken algorithm on the original input matrix, we form a new larger matrix by sampling and run a single iteration of the broken algorithm. Asymptotically, the resulting algorithm has runtime $O(n^{\frac{3 \log6}{\log7}} \log n) \leq O(n^{2.763})$, a slight improvement of Karppa-Kaski's algorithm. Since the goal is to obtain new practical matrix-multiplication algorithms, these asymptotic runtime bounds are not directly useful. We estimate the runtime for our algorithm for some sample problems which are at the upper limits of practical algorithms; unfortunately, for these parameters, the new algorithm does not appear to be beneficial.
In this paper, we analyze the performance of a reconfigurable intelligent surface (RIS)-assisted multi-hop transmission by employing multiple RIS units to enable favorable communication for a mixed free-space optical (FSO) and radio-frequency (RF) system. We consider a single-element RIS since it is hard to realize phase compensation for multiple-element RIS in the multi-hop scenario. We develop statistical results for the product of the signal-to-noise ratio (SNR) of the cascaded multiple RIS-equipped wireless communication. We use decode-and-forward (DF) and fixed-gain (FG) relaying protocols to mix multi-RIS transmissions over RF and FSO technologies and derive probability density and distribution functions for both the relaying schemes by considering independent and nonidentical double generalized gamma (dGG) distribution models for RF transmissions with line-of-sight (LOS) and inverse-Gamma shadowing effect and atmospheric turbulence for FSO system combined with pointing errors. We analyze the outage probability, and average bit-error rate (BER) performance of the considered system. We also present an asymptotic analysis of the outage probability using gamma functions to provide insight into the considered system in the high SNR regime. We use computer simulations to validate the derived analytical expressions and demonstrate the performance for different system parameters on the RIS-assisted multi-hop transmissions for a vehicular communication system.
The main contribution of this paper is a new improved variant of the laser method for designing matrix multiplication algorithms. Building upon the recent techniques of [Duan, Wu, Zhou FOCS'2023], the new method introduces several new ingredients that not only yield an improved bound on the matrix multiplication exponent $\omega$, but also improves the known bounds on rectangular matrix multiplication by [Le Gall and Urrutia SODA'2018]. In particular, the new bound on $\omega$ is $\omega \le 2.371552$ (improved from $\omega \le 2.371866$). For the dual matrix multiplication exponent $\alpha$ defined as the largest $\alpha$ for which $\omega(1, \alpha, 1) = 2$, we obtain the improvement $\alpha \ge 0.321334$ (improved from $\alpha \ge 0.31389$). Similar improvements are obtained for various other exponents for multiplying rectangular matrices.
In this paper we derive tight lower bounds resolving the hardness status of several fundamental weighted matroid problems. One notable example is budgeted matroid independent set, for which we show there is no fully polynomial-time approximation scheme (FPTAS), indicating the Efficient PTAS of [Doron-Arad, Kulik and Shachnai, SOSA 2023] is the best possible. Furthermore, we show that there is no pseudo-polynomial time algorithm for exact weight matroid independent set, implying the algorithm of [Camerini, Galbiati and Maffioli, J. Algorithms 1992] for representable matroids cannot be generalized to arbitrary matroids. Similarly, we show there is no Fully PTAS for constrained minimum basis of a matroid and knapsack cover with a matroid, implying the existing Efficient PTAS for the former is optimal. For all of the above problems, we obtain unconditional lower bounds in the oracle model, where the independent sets of the matroid can be accessed only via a membership oracle. We complement these results by showing that the same lower bounds hold under standard complexity assumptions, even if the matroid is encoded as part of the instance. All of our bounds are based on a specifically structured family of paving matroids.
In this paper, we extend the Generalized Finite Difference Method (GFDM) on unknown compact submanifolds of the Euclidean domain, identified by randomly sampled data that (almost surely) lie on the interior of the manifolds. Theoretically, we formalize GFDM by exploiting a representation of smooth functions on the manifolds with Taylor's expansions of polynomials defined on the tangent bundles. We illustrate the approach by approximating the Laplace-Beltrami operator, where a stable approximation is achieved by a combination of Generalized Moving Least-Squares algorithm and novel linear programming that relaxes the diagonal-dominant constraint for the estimator to allow for a feasible solution even when higher-order polynomials are employed. We establish the theoretical convergence of GFDM in solving Poisson PDEs and numerically demonstrate the accuracy on simple smooth manifolds of low and moderate high co-dimensions as well as unknown 2D surfaces. For the Dirichlet Poisson problem where no data points on the boundaries are available, we employ GFDM with the volume-constraint approach that imposes the boundary conditions on data points close to the boundary. When the location of the boundary is unknown, we introduce a novel technique to detect points close to the boundary without needing to estimate the distance of the sampled data points to the boundary. We demonstrate the effectiveness of the volume-constraint employed by imposing the boundary conditions on the data points detected by this new technique compared to imposing the boundary conditions on all points within a certain distance from the boundary, where the latter is sensitive to the choice of truncation distance and require the knowledge of the boundary location.
Denoising low-dose computed tomography (CT) images is a critical task in medical image computing. Supervised deep learning-based approaches have made significant advancements in this area in recent years. However, these methods typically require pairs of low-dose and normal-dose CT images for training, which are challenging to obtain in clinical settings. Existing unsupervised deep learning-based methods often require training with a large number of low-dose CT images or rely on specially designed data acquisition processes to obtain training data. To address these limitations, we propose a novel unsupervised method that only utilizes normal-dose CT images during training, enabling zero-shot denoising of low-dose CT images. Our method leverages the diffusion model, a powerful generative model. We begin by training a cascaded unconditional diffusion model capable of generating high-quality normal-dose CT images from low-resolution to high-resolution. The cascaded architecture makes the training of high-resolution diffusion models more feasible. Subsequently, we introduce low-dose CT images into the reverse process of the diffusion model as likelihood, combined with the priors provided by the diffusion model and iteratively solve multiple maximum a posteriori (MAP) problems to achieve denoising. Additionally, we propose methods to adaptively adjust the coefficients that balance the likelihood and prior in MAP estimations, allowing for adaptation to different noise levels in low-dose CT images. We test our method on low-dose CT datasets of different regions with varying dose levels. The results demonstrate that our method outperforms the state-of-the-art unsupervised method and surpasses several supervised deep learning-based methods. Codes are available in //github.com/DeepXuan/Dn-Dp.
We introduce a new method of estimation of parameters in semiparametric and nonparametric models. The method is based on estimating equations that are $U$-statistics in the observations. The $U$-statistics are based on higher order influence functions that extend ordinary linear influence functions of the parameter of interest, and represent higher derivatives of this parameter. For parameters for which the representation cannot be perfect the method leads to a bias-variance trade-off, and results in estimators that converge at a slower than $\sqrt n$-rate. In a number of examples the resulting rate can be shown to be optimal. We are particularly interested in estimating parameters in models with a nuisance parameter of high dimension or low regularity, where the parameter of interest cannot be estimated at $\sqrt n$-rate, but we also consider efficient $\sqrt n$-estimation using novel nonlinear estimators. The general approach is applied in detail to the example of estimating a mean response when the response is not always observed.
Duan, Wu and Zhou (FOCS 2023) recently obtained the improved upper bound on the exponent of square matrix multiplication $\omega<2.3719$ by introducing a new approach to quantify and compensate the ``combination loss" in prior analyses of powers of the Coppersmith-Winograd tensor. In this paper we show how to use this new approach to improve the exponent of rectangular matrix multiplication as well. Our main technical contribution is showing how to combine this analysis of the combination loss and the analysis of the fourth power of the Coppersmith-Winograd tensor in the context of rectangular matrix multiplication developed by Le Gall and Urrutia (SODA 2018).
Since deep neural networks were developed, they have made huge contributions to everyday lives. Machine learning provides more rational advice than humans are capable of in almost every aspect of daily life. However, despite this achievement, the design and training of neural networks are still challenging and unpredictable procedures. To lower the technical thresholds for common users, automated hyper-parameter optimization (HPO) has become a popular topic in both academic and industrial areas. This paper provides a review of the most essential topics on HPO. The first section introduces the key hyper-parameters related to model training and structure, and discusses their importance and methods to define the value range. Then, the research focuses on major optimization algorithms and their applicability, covering their efficiency and accuracy especially for deep learning networks. This study next reviews major services and toolkits for HPO, comparing their support for state-of-the-art searching algorithms, feasibility with major deep learning frameworks, and extensibility for new modules designed by users. The paper concludes with problems that exist when HPO is applied to deep learning, a comparison between optimization algorithms, and prominent approaches for model evaluation with limited computational resources.
With the rapid increase of large-scale, real-world datasets, it becomes critical to address the problem of long-tailed data distribution (i.e., a few classes account for most of the data, while most classes are under-represented). Existing solutions typically adopt class re-balancing strategies such as re-sampling and re-weighting based on the number of observations for each class. In this work, we argue that as the number of samples increases, the additional benefit of a newly added data point will diminish. We introduce a novel theoretical framework to measure data overlap by associating with each sample a small neighboring region rather than a single point. The effective number of samples is defined as the volume of samples and can be calculated by a simple formula $(1-\beta^{n})/(1-\beta)$, where $n$ is the number of samples and $\beta \in [0,1)$ is a hyperparameter. We design a re-weighting scheme that uses the effective number of samples for each class to re-balance the loss, thereby yielding a class-balanced loss. Comprehensive experiments are conducted on artificially induced long-tailed CIFAR datasets and large-scale datasets including ImageNet and iNaturalist. Our results show that when trained with the proposed class-balanced loss, the network is able to achieve significant performance gains on long-tailed datasets.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191