More Like this

1. Template-based piecewise affine regression

   https://doi.org/10.1017/cbp.2024.3  

   Berger, Guillaume O; Sankaranarayanan, Sriram (January 2024, Research Directions: Cyber-Physical Systems)

   Abstract We study the problem of fitting a piecewise affine (PWA) function to input–output data. Our algorithm divides the input domain into finitely many regions whose shapes are specified by a user-provided template and such that the input–output data in each region are fit by an affine function within a user-provided error tolerance. We first prove that this problem is NP-hard. Then, we present a top-down algorithmic approach for solving the problem. The algorithm considers subsets of the data points in a systematic manner, trying to fit an affine function for each subset using linear regression. If regression fails on a subset, the algorithm extracts a minimal set of points from the subset (an unsatisfiable core) that is responsible for the failure. The identified core is then used to split the current subset into smaller ones. By combining this top-down scheme with a set-covering algorithm, we derive an overall approach that provides optimal PWA models for a given error tolerance, where optimality refers to minimizing the number of pieces of the PWA model. We demonstrate our approach on three numerical examples that include PWA approximations of a widely used nonlinear insulin–glucose regulation model and a double inverted pendulum with soft contacts. 

   more » « less
2. CRISPR-Cas effector specificity and cleavage site determine phage escape outcomes

   https://doi.org/10.1371/journal.pbio.3002065  

   Schelling, Michael A.; Nguyen, Giang T.; Sashital, Dipali G. (April 2023, PLOS Biology)

   Barr, Jeremy J. (Ed.)

   CRISPR-mediated interference relies on complementarity between a guiding CRISPR RNA (crRNA) and target nucleic acids to provide defense against bacteriophage. Phages escape CRISPR-based immunity mainly through mutations in the protospacer adjacent motif (PAM) and seed regions. However, previous specificity studies of Cas effectors, including the class 2 endonuclease Cas12a, have revealed a high degree of tolerance of single mismatches. The effect of this mismatch tolerance has not been extensively studied in the context of phage defense. Here, we tested defense against lambda phage provided by Cas12a-crRNAs containing preexisting mismatches against the genomic targets in phage DNA. We find that most preexisting crRNA mismatches lead to phage escape, regardless of whether the mismatches ablate Cas12a cleavage in vitro. We used high-throughput sequencing to examine the target regions of phage genomes following CRISPR challenge. Mismatches at all locations in the target accelerated emergence of mutant phage, including mismatches that greatly slowed cleavage in vitro. Unexpectedly, our results reveal that a preexisting mismatch in the PAM-distal region results in selection of mutations in the PAM-distal region of the target. In vitro cleavage and phage competition assays show that dual PAM-distal mismatches are significantly more deleterious than combinations of seed and PAM-distal mismatches, resulting in this selection. However, similar experiments with Cas9 did not result in emergence of PAM-distal mismatches, suggesting that cut-site location and subsequent DNA repair may influence the location of escape mutations within target regions. Expression of multiple mismatched crRNAs prevented new mutations from arising in multiple targeted locations, allowing Cas12a mismatch tolerance to provide stronger and longer-term protection. These results demonstrate that Cas effector mismatch tolerance, existing target mismatches, and cleavage site strongly influence phage evolution. 

   more » « less
3. Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA

   Kumar, S; Pandey, S; Sarkar, P (June 2025, https://doi.org/10.48550/arXiv.2506.12655)

   We propose a novel statistical inference framework for streaming principal component analysis (PCA) using Oja's algorithm, enabling the construction of confidence intervals for individual entries of the estimated eigenvector. Most existing works on streaming PCA focus on providing sharp sin-squared error guarantees. Recently, there has been some interest in uncertainty quantification for the sin-squared error. However, uncertainty quantification or sharp error guarantees for entries of the estimated eigenvector in the streaming setting remains largely unexplored. We derive a sharp Bernstein-type concentration bound for elements of the estimated vector matching the optimal error rate up to logarithmic factors. We also establish a Central Limit Theorem for a suitably centered and scaled subset of the entries. To efficiently estimate the coordinate-wise variance, we introduce a provably consistent subsampling algorithm that leverages the median-of-means approach, empirically achieving similar accuracy to multiplier bootstrap methods while being significantly more computationally efficient. Numerical experiments demonstrate its effectiveness in providing reliable uncertainty estimates with a fraction of the computational cost of existing methods. 

   more » « less
4. Demonstration of the rodeo algorithm on a quantum computer

   https://doi.org/10.1140/epja/s10050-024-01373-9  

   Qian, Zhengrong; Watkins, Jacob; Given, Gabriel; Bonitati, Joey; Choi, Kenneth; Lee, Dean (July 2024, The European Physical Journal A)

   The rodeo algorithm is an efficient algorithm for eigenstate preparation and eigenvalue estimation for any observable on a quantum computer. This makes it a promising tool for studying the spectrum and structure of atomic nuclei as well as other fields of quantum many-body physics. The only requirement is that the initial state has sufficient overlap probability with the desired eigenstate. While it is exponentially faster than well-known algorithms such as phase estimation and adiabatic evolution for eigenstate preparation, it has yet to be implemented on an actual quantum device. In this work, we apply the rodeo algorithm to determine the energy levels of a random one-qubit Hamiltonian, resulting in a relative error of 0.08% using mid-circuit measurements on the IBM Q device Casablanca. This surpasses the accuracy of directly-prepared eigenvector expectation values using the same quantum device. We take advantage of the high-accuracy energy determination and use the Hellmann-Feynman theorem to compute eigenvector expectation values for a different random one-qubit observable. For the Hellmann-Feynman calculations, we find a relative error of 0.7%. We conclude by discussing possible future applications of the rodeo algorithm for multi-qubit Hamiltonians. 

   more » « less
5. Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering

   https://doi.org/10.3389/fdata.2023.1020173  

   Zhu, Yu; Segarra, Santiago (February 2023, Frontiers in Big Data)

   We study p -Laplacians and spectral clustering for a recently proposed hypergraph model that incorporates edge-dependent vertex weights (EDVW). These weights can reflect different importance of vertices within a hyperedge, thus conferring the hypergraph model higher expressivity and flexibility. By constructing submodular EDVW-based splitting functions, we convert hypergraphs with EDVW into submodular hypergraphs for which the spectral theory is better developed. In this way, existing concepts and theorems such as p -Laplacians and Cheeger inequalities proposed under the submodular hypergraph setting can be directly extended to hypergraphs with EDVW. For submodular hypergraphs with EDVW-based splitting functions, we propose an efficient algorithm to compute the eigenvector associated with the second smallest eigenvalue of the hypergraph 1-Laplacian. We then utilize this eigenvector to cluster the vertices, achieving higher clustering accuracy than traditional spectral clustering based on the 2-Laplacian. More broadly, the proposed algorithm works for all submodular hypergraphs that are graph reducible. Numerical experiments using real-world data demonstrate the effectiveness of combining spectral clustering based on the 1-Laplacian and EDVW. 

   more » « less