BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Yihong Wu

Yihong Wu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.STStatistics TheoryInformation Theorymath.ITMachine Learningcond-mat.mes-hallmath.PRcond-mat.mtrl-sciphysics.app-phastro-ph.SRData Structures and AlgorithmsSocial and Information NetworksComputer Visionphysics.opticsphysics.space-phArtificial Intelligenceastro-ph.HEastro-ph.IMComputationComputational Complexitycond-mat.str-elmath.COmath.OCMethodologyRobotics

Catalog footprint

What is connected

59works
25topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

59 published item(s)

preprint2026arXiv

Confidence-Aware Alignment Makes Reasoning LLMs More Reliable

Large reasoning models often reach correct answers through flawed intermediate steps, creating a gap between final accuracy and reasoning reliability. Existing alignment strategies address this with external verifiers or massive sampling, limiting scalability. In this work, we introduce CASPO (Confidence-Aware Step-wise Preference Optimization), a framework that aligns token-level confidence with step-wise logical correctness through iterative Direct Preference Optimization, without training a separate reward model. During inference, we propose Confidence-aware Thought (CaT), which leverages this calibrated confidence to dynamically prune uncertain reasoning branches with negligible O(V) latency. Experiments across ten benchmarks and multiple model families show that CASPO consistently improves reasoning reliability and inference efficiency. CASPO scales to Qwen3-8B-Base and surpasses tree-search baselines on AIME'24 and AIME'25 without using reward-model data. We also release a step-wise dataset with confidence annotations to support fine-grained analysis of reasoning reliability. Code is available at https://github.com/Thecommonirin/CASPO.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A vector magnetometer based on a single spin-orbit torque anomalous Hall device

In many applications, the ability to measure the vector information of a magnetic field with high spatial resolution and low cost is essential, but it is still a challenge for existing magnetometers composed of multiple sensors. Here, we report a single-device based vector magnetometer, which is enabled by spin-orbit torque, capable of measuring a vector magnetic field using the harmonic Hall resistances of a superparamagnetic ferromagnet (FM)/heavy metal (HM) bilayer. Under an ac driving current, the first and second harmonic Hall resistances of the FM/HM bilayer show a linear relationship with the vertical and longitudinal component (along the current direction) of the magnetic field, respectively. By employing a L-shaped Hall device with two orthogonal arms, we can measure all the three field components simultaneously, so as to detect both the amplitude and direction of magnetic field in a three-dimensional space. As proof of concepts, we demonstrate both angular position sensing on the three coordinate planes and vector mapping of magnetic field generated by a permanent magnet, both of which are in good agreement with the simulation results. Crosstalk between vertical and longitudinal field components at large field is discussed using theoretical models.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Learning Mixtures of Permutations: Groups of Pairwise Comparisons and Combinatorial Method of Moments

In applications such as rank aggregation, mixture models for permutations are frequently used when the population exhibits heterogeneity. In this work, we study the widely used Mallows mixture model. In the high-dimensional setting, we propose a polynomial-time algorithm that learns a Mallows mixture of permutations on $n$ elements with the optimal sample complexity that is proportional to $\log n$, improving upon previous results that scale polynomially with $n$. In the high-noise regime, we characterize the optimal dependency of the sample complexity on the noise parameter. Both objectives are accomplished by first studying demixing permutations under a noiseless query model using groups of pairwise comparisons, which can be viewed as moments of the mixing distribution, and then extending these results to the noisy Mallows model by simulating the noiseless oracle.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Lightweight Object-level Topological Semantic Mapping and Long-term Global Localization based on Graph Matching

Mapping and localization are two essential tasks for mobile robots in real-world applications. However, largescale and dynamic scenes challenge the accuracy and robustness of most current mature solutions. This situation becomes even worse when computational resources are limited. In this paper, we present a novel lightweight object-level mapping and localization method with high accuracy and robustness. Different from previous methods, our method does not need a prior constructed precise geometric map, which greatly releases the storage burden, especially for large-scale navigation. We use object-level features with both semantic and geometric information to model landmarks in the environment. Particularly, a learning topological primitive is first proposed to efficiently obtain and organize the object-level landmarks. On the basis of this, we use a robot-centric mapping framework to represent the environment as a semantic topology graph and relax the burden of maintaining global consistency at the same time. Besides, a hierarchical memory management mechanism is introduced to improve the efficiency of online mapping with limited computational resources. Based on the proposed map, the robust localization is achieved by constructing a novel local semantic scene graph descriptor, and performing multi-constraint graph matching to compare scene similarity. Finally, we test our method on a low-cost embedded platform to demonstrate its advantages. Experimental results on a large scale and multi-session real-world environment show that the proposed method outperforms the state of arts in terms of lightweight and robustness.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal prediction of Markov chains with and without spectral gap

We study the following learning problem with dependent data: Observing a trajectory of length $n$ from a stationary Markov chain with $k$ states, the goal is to predict the next state. For $3 \leq k \leq O(\sqrt{n})$, using techniques from universal compression, the optimal prediction risk in Kullback-Leibler divergence is shown to be $Θ(\frac{k^2}{n}\log \frac{n}{k^2})$, in contrast to the optimal rate of $Θ(\frac{\log \log n}{n})$ for $k=2$ previously shown in Falahatgar et al. (2016). These rates, slower than the parametric rate of $O(\frac{k^2}{n})$, can be attributed to the memory in the data, as the spectral gap of the Markov chain can be arbitrarily small. To quantify the memory effect, we study irreducible reversible chains with a prescribed spectral gap. In addition to characterizing the optimal prediction risk for two states, we show that, as long as the spectral gap is not excessively small, the prediction risk in the Markov model is $O(\frac{k^2}{n})$, which coincides with that of an iid model with the same number of parameters. Extensions to higher-order Markov chains are also obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Random Graph Matching in Geometric Models: the Case of Complete Graphs

This paper studies the problem of matching two complete graphs with edge weights correlated through latent geometries, extending a recent line of research on random graph matching with independent edge weights to geometric models. Specifically, given a random permutation $π^*$ on $[n]$ and $n$ iid pairs of correlated Gaussian vectors $\{X_{π^*(i)}, Y_i\}$ in $\mathbb{R}^d$ with noise parameter $σ$, the edge weights are given by $A_{ij}=κ(X_i,X_j)$ and $B_{ij}=κ(Y_i,Y_j)$ for some link function $κ$. The goal is to recover the hidden vertex correspondence $π^*$ based on the observation of $A$ and $B$. We focus on the dot-product model with $κ(x,y)=\langle x, y \rangle$ and Euclidean distance model with $κ(x,y)=\|x-y\|^2$, in the low-dimensional regime of $d=o(\log n)$ wherein the underlying geometric structures are most evident. We derive an approximate maximum likelihood estimator, which provably achieves, with high probability, perfect recovery of $π^*$ when $σ=o(n^{-2/d})$ and almost perfect recovery with a vanishing fraction of errors when $σ=o(n^{-1/d})$. Furthermore, these conditions are shown to be information-theoretically optimal even when the latent coordinates $\{X_i\}$ and $\{Y_i\}$ are observed, complementing the recent results of [DCK19] and [KNW22] in geometric models of the planted bipartite matching problem. As a side discovery, we show that the celebrated spectral algorithm of [Ume88] emerges as a further approximation to the maximum likelihood in the geometric model.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Settling the Sharp Reconstruction Thresholds of Random Graph Matching

This paper studies the problem of recovering the hidden vertex correspondence between two edge-correlated random graphs. We focus on the Gaussian model where the two graphs are complete graphs with correlated Gaussian weights and the Erdős-Rényi model where the two graphs are subsampled from a common parent Erdős-Rényi graph $\mathcal{G}(n,p)$. For dense graphs with $p=n^{-o(1)}$, we prove that there exists a sharp threshold, above which one can correctly match all but a vanishing fraction of vertices and below which correctly matching any positive fraction is impossible, a phenomenon known as the "all-or-nothing" phase transition. Even more strikingly, in the Gaussian setting, above the threshold all vertices can be exactly matched with high probability. In contrast, for sparse Erdős-Rényi graphs with $p=n^{-Θ(1)}$, we show that the all-or-nothing phenomenon no longer holds and we determine the thresholds up to a constant factor. Along the way, we also derive the sharp threshold for exact recovery, sharpening the existing results in Erdős-Rényi graphs. The proof of the negative results builds upon a tight characterization of the mutual information based on the truncated second-moment computation and an "area theorem" that relates the mutual information to the integral of the reconstruction error. The positive results follows from a tight analysis of the maximum likelihood estimator that takes into account the cycle structure of the induced permutation on the edges.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Testing network correlation efficiently via counting trees

We propose a new procedure for testing whether two networks are edge-correlated through some latent vertex correspondence. The test statistic is based on counting the co-occurrences of signed trees for a family of non-isomorphic trees. When the two networks are Erdős-Rényi random graphs $\mathcal{G}(n,q)$ that are either independent or correlated with correlation coefficient $ρ$, our test runs in $n^{2+o(1)}$ time and succeeds with high probability as $n\to\infty$, provided that $n\min\{q,1-q\} \ge n^{-o(1)}$ and $ρ^2>α\approx 0.338$, where $α$ is Otter's constant so that the number of unlabeled trees with $K$ edges grows as $(1/α)^K$. This significantly improves the prior work in terms of statistical accuracy, running time, and graph sparsity.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

VisImages: A Fine-Grained Expert-Annotated Visualization Dataset

Images in visualization publications contain rich information, e.g., novel visualization designs and implicit design patterns of visualizations. A systematic collection of these images can contribute to the community in many aspects, such as literature analysis and automated tasks for visualization. In this paper, we build and make public a dataset, VisImages, which collects 12,267 images with captions from 1,397 papers in IEEE InfoVis and VAST. Built upon a comprehensive visualization taxonomy, the dataset includes 35,096 visualizations and their bounding boxes in the images.We demonstrate the usefulness of VisImages through three use cases: 1) investigating the use of visualizations in the publications with VisImages Explorer, 2) training and benchmarking models for visualization classification, and 3) localizing visualizations in the visual analytics systems automatically.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Dualizing Le Cam's method for functional estimation, with applications to estimating the unseens

Le Cam's method (or the two-point method) is a commonly used tool for obtaining statistical lower bound and especially popular for functional estimation problems. This work aims to explain and give conditions for the tightness of Le Cam's lower bound in functional estimation from the perspective of convex duality. Under a variety of settings it is shown that the maximization problem that searches for the best two-point lower bound, upon dualizing, becomes a minimization problem that optimizes the bias-variance tradeoff among a family of estimators. For estimating linear functionals of a distribution our work strengthens prior results of Donoho-Liu \cite{DL91} (for quadratic loss) by dropping the Hölderian assumption on the modulus of continuity. For exponential families our results extend those of Juditsky-Nemirovski \cite{JN09} by characterizing the minimax risk for the quadratic loss under weaker assumptions on the exponential family. We also provide an extension to the high-dimensional setting for estimating separable functionals. Notably, coupled with tools from complex analysis, this method is particularly effective for characterizing the ``elbow effect'' -- the phase transition from parametric to nonparametric rates. As the main application we derive sharp minimax rates in the Distinct elements problem (given a fraction $p$ of colored balls from an urn containing $d$ balls, the optimal error of estimating the number of distinct colors is $\tilde Θ(d^{-\frac{1}{2}\min\{\frac{p}{1-p},1\}})$) and the Fisher's species problem (given $n$ iid observations from an unknown distribution, the optimal prediction error of the number of unseen symbols in the next (unobserved) $r \cdot n$ observations is $\tilde Θ(n^{-\min\{\frac{1}{r+1},\frac{1}{2}\}})$).

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model

We study the non-convex optimization landscape for maximum likelihood estimation in the discrete orbit recovery model with Gaussian noise. This model is motivated by applications in molecular microscopy and image processing, where each measurement of an unknown object is subject to an independent random rotation from a rotational group. Equivalently, it is a Gaussian mixture model where the mixture centers belong to a group orbit. We show that fundamental properties of the likelihood landscape depend on the signal-to-noise ratio and the group structure. At low noise, this landscape is "benign" for any discrete group, possessing no spurious local optima and only strict saddle points. At high noise, this landscape may develop spurious local optima, depending on the specific group. We discuss several positive and negative examples, and provide a general condition that ensures a globally benign landscape. For cyclic permutations of coordinates on $\mathbb{R}^d$ (multi-reference alignment), there may be spurious local optima when $d \geq 6$, and we establish a correspondence between these local optima and those of a surrogate function of the phase variables in the Fourier domain. We show that the Fisher information matrix transitions from resembling that of a single Gaussian in low noise to having a graded eigenvalue structure in high noise, which is determined by the graded algebra of invariant polynomials under the group action. In a local neighborhood of the true object, the likelihood landscape is strongly convex in a reparametrized system of variables given by a transcendence basis of this polynomial algebra. We discuss implications for optimization algorithms, including slow convergence of expectation-maximization, and possible advantages of momentum-based acceleration and variable reparametrization for first- and second-order descent methods.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Testing correlation of unlabeled random graphs

We study the problem of detecting the edge correlation between two random graphs with $n$ unlabeled nodes. This is formalized as a hypothesis testing problem, where under the null hypothesis, the two graphs are independently generated; under the alternative, the two graphs are edge-correlated under some latent node correspondence, but have the same marginal distributions as the null. For both Gaussian-weighted complete graphs and dense Erdős-Rényi graphs (with edge probability $n^{-o(1)}$), we determine the sharp threshold at which the optimal testing error probability exhibits a phase transition from zero to one as $n\to \infty$. For sparse Erdős-Rényi graphs with edge probability $n^{-Ω(1)}$, we determine the threshold within a constant factor. The proof of the impossibility results is an application of the conditional second-moment method, where we bound the truncated second moment of the likelihood ratio by carefully conditioning on the typical behavior of the intersection graph (consisting of edges in both observed graphs) and taking into account the cycle structure of the induced random permutation on the edges. Notably, in the sparse regime, this is accomplished by leveraging the pseudoforest structure of subcritical Erdős-Rényi graphs and a careful enumeration of subpseudoforests that can be assembled from short orbits of the edge permutation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Application of information-percolation method to reconstruction problems on graphs

In this paper we propose a method of proving impossibility results based on applying strong data-processing inequalities to estimate mutual information between sets of variables forming certain Markov random fields. The end result is that mutual information between two "far away" (as measured by the graph distance) variables is bounded by the probability of the existence of an open path in a bond-percolation problem on the same graph. Furthermore, stronger bounds can be obtained by establishing mutual information comparison results with an erasure model on the same graph, with erasure probabilities given by the contraction coefficients. As applications, we show that our method gives sharp threshold for partially recovering a rank-one perturbation of a random Gaussian matrix (spiked Wigner model), yields the best known upper bound on the noise level for group synchronization (obtained concurrently by Abbe and Boix), and establishes new impossibility result for community detection on the stochastic block model with $k$ communities.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Eddy Current Testing of Metal Cracks Using Spin Hall Magnetoresistance Sensor and Machine Learning

Recently we have developed a spin Hall magnetoresistance (SMR) sensor which operates under AC bias and sense currents. Here we demonstrate both theoretically and experimentally that the SMR sensor is uniquely suited for eddy current testing applications because both the coil and sensor utilize AC current as the excitation source. The use of SMR sensor effectively eliminates the necessity of any demodulation or lock-in technique for detecting the eddy current, which greatly simplifies the detection system. Furthermore, we show that the combination of principal component analysis and decision tree model is effective in classifying the metal cracks. The relatively clean signals obtained by the SMR sensor greatly facilitates the subsequent signal analysis and ensures high accuracy in the classification of different types of crack features.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Efficient random graph matching via degree profiles

Random graph matching refers to recovering the underlying vertex correspondence between two random graphs with correlated edges; a prominent example is when the two random graphs are given by Erdős-Rényi graphs $G(n,\frac{d}{n})$. This can be viewed as an average-case and noisy version of the graph isomorphism problem. Under this model, the maximum likelihood estimator is equivalent to solving the intractable quadratic assignment problem. This work develops an $\tilde{O}(n d^2+n^2)$-time algorithm which perfectly recovers the true vertex correspondence with high probability, provided that the average degree is at least $d = Ω(\log^2 n)$ and the two graphs differ by at most $δ= O( \log^{-2}(n) )$ fraction of edges. For dense graphs and sparse graphs, this can be improved to $δ= O( \log^{-2/3}(n) )$ and $δ= O( \log^{-2}(d) )$ respectively, both in polynomial time. The methodology is based on appropriately chosen distance statistics of the degree profiles (empirical distribution of the degrees of neighbors). Before this work, the best known result achieves $δ=O(1)$ and $n^{o(1)} \leq d \leq n^c$ for some constant $c$ with an $n^{O(\log n)}$-time algorithm \cite{barak2018nearly} and $δ=\tilde O((d/n)^4)$ and $d = \tildeΩ(n^{4/5})$ with a polynomial-time algorithm \cite{dai2018performance}.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Evidence for a Coronal Shock Wave Origin for Relativistic Protons Producing Solar Gamma-Rays and Observed by Neutron Monitors at Earth

We study the solar eruptive event on 2017 September 10 that produced long-lasting $>$100 MeV $γ$-ray emission and a ground level enhancement (GLE72). The origin of the high-energy ions producing late-phase gamma-ray emission (LPGRE) is still an open question, but a possible explanation is proton acceleration at coronal shocks produced by coronal mass ejections. We examine a common shock acceleration origin for both the LPGRE and GLE72. The $γ$-ray emission observed by the Fermi-Large Area Telescope exhibits a weak impulsive phase, consistent with that observed in hard X-and $γ$-ray line flare emissions, and what appear to be two distinct stages of LPGRE. From a detailed modeling of the shock wave, we derive the 3D distribution and temporal evolution of the shock parameters, and we examine the shock wave magnetic connection with the visible solar disk. The evolution of shock parameters on field lines returning to the visible disk, mirrors the two stages of LPGRE. We find good agreement between the time history of $>$100 MeV $γ$-rays and one produced by a basic shock acceleration model. The time history of shock parameters magnetically mapped to Earth agrees with the rates observed by the Fort Smith neutron monitor during the first hour of the GLE72 if we include a 30% contribution of flare-accelerated protons during the first 10 minutes, having a release time following the time history of nuclear $γ$-rays. Our analysis provides compelling evidence for a common shock origin for protons producing the LPGRE and most of the particles observed in GLE72.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Extrapolating the profile of a finite population

We study a prototypical problem in empirical Bayes. Namely, consider a population consisting of $k$ individuals each belonging to one of $k$ types (some types can be empty). Without any structural restrictions, it is impossible to learn the composition of the full population having observed only a small (random) subsample of size $m = o(k)$. Nevertheless, we show that in the sublinear regime of $m =ω(k/\log k)$, it is possible to consistently estimate in total variation the \emph{profile} of the population, defined as the empirical distribution of the sizes of each type, which determines many symmetric properties of the population. We also prove that in the linear regime of $m=c k$ for any constant $c$ the optimal rate is $Θ(1/\log k)$. Our estimator is based on Wolfowitz's minimum distance method, which entails solving a linear program (LP) of size $k$. We show that there is a single infinite-dimensional LP whose value simultaneously characterizes the risk of the minimum distance estimator and certifies its minimax optimality. The sharp convergence rate is obtained by evaluating this LP using complex-analytic techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Note on approximating the Laplace transform of a Gaussian on a complex disk

In this short note we study how well a Gaussian distribution can be approximated by distributions supported on $[-a,a]$. Perhaps, the natural conjecture is that for large $a$ the almost optimal choice is given by truncating the Gaussian to $[-a,a]$. Indeed, such approximation achieves the optimal rate of $e^{-Θ(a^2)}$ in terms of the $L_\infty$-distance between characteristic functions. However, if we consider the $L_\infty$-distance between Laplace transforms on a complex disk, the optimal rate is $e^{-Θ(a^2 \log a)}$, while truncation still only attains $e^{-Θ(a^2)}$. The optimal rate can be attained by the Gauss-Hermite quadrature. As corollary, we also construct a ``super-flat'' Gaussian mixture of $Θ(a^2)$ components with means in $[-a,a]$ and whose density has all derivatives bounded by $e^{-Ω(a^2 \log(a))}$ in the $O(1)$-neighborhood of the origin.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Relating streamer flows to density and magnetic structures at the Parker Solar Probe

The physical mechanisms that produce the slow solar wind are still highly debated. Parker Solar Probe's (PSP's) second solar encounter provided a new opportunity to relate in situ measurements of the nascent slow solar wind with white-light images of streamer flows. We exploit data taken by the Solar and Heliospheric Observatory (SOHO), the Solar TErrestrial RElations Observatory (STEREO) and the Wide Imager on Solar Probe to reveal for the first time a close link between imaged streamer flows and the high-density plasma measured by the Solar Wind Electrons Alphas and Protons (SWEAP) experiment. We identify different types of slow winds measured by PSP that we relate to the spacecraft's magnetic connectivity (or not) to streamer flows. SWEAP measured high-density and highly variable plasma when PSP was well connected to streamers but more tenuous wind with much weaker density variations when it exited streamer flows. STEREO imaging of the release and propagation of small transients from the Sun to PSP reveals that the spacecraft was continually impacted by the southern edge of streamer transients. The impact of specific density structures is marked by a higher occurrence of magnetic field reversals measured by the FIELDS magnetometers. Magnetic reversals originating from the streamers are associated with larger density variations compared with reversals originating outside streamers. We tentatively interpret these findings in terms of magnetic reconnection between open magnetic fields and coronal loops with different properties, providing support for the formation of a subset of the slow wind by magnetic reconnection.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Sample complexity of population recovery

The problem of population recovery refers to estimating a distribution based on incomplete or corrupted samples. Consider a random poll of sample size $n$ conducted on a population of individuals, where each pollee is asked to answer $d$ binary questions. We consider one of the two polling impediments: (a) in lossy population recovery, a pollee may skip each question with probability $ε$, (b) in noisy population recovery, a pollee may lie on each question with probability $ε$. Given $n$ lossy or noisy samples, the goal is to estimate the probabilities of all $2^d$ binary vectors simultaneously within accuracy $δ$ with high probability. This paper settles the sample complexity of population recovery. For lossy model, the optimal sample complexity is $\tildeΘ(δ^{-2\max\{\fracε{1-ε},1\}})$, improving the state of the art by Moitra and Saks in several ways: a lower bound is established, the upper bound is improved and the result depends at most on the logarithm of the dimension. Surprisingly, the sample complexity undergoes a phase transition from parametric to nonparametric rate when $ε$ exceeds $1/2$. For noisy population recovery, the sharp sample complexity turns out to be more sensitive to dimension and scales as $\exp(Θ(d^{1/3} \log^{2/3}(1/δ)))$ except for the trivial cases of $ε=0,1/2$ or $1$. For both models, our estimators simply compute the empirical mean of a certain function, which is found by pre-solving a linear program (LP). Curiously, the dual LP can be understood as Le Cam's method for lower-bounding the minimax risk, thus establishing the statistical optimality of the proposed estimators. The value of the LP is determined by complex-analytic methods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Self-regularizing Property of Nonparametric Maximum Likelihood Estimator in Mixture Models

Introduced by Kiefer and Wolfowitz \cite{KW56}, the nonparametric maximum likelihood estimator (NPMLE) is a widely used methodology for learning mixture odels and empirical Bayes estimation. Sidestepping the non-convexity in mixture likelihood, the NPMLE estimates the mixing distribution by maximizing the total likelihood over the space of probability measures, which can be viewed as an extreme form of overparameterization. In this paper we discover a surprising property of the NPMLE solution. Consider, for example, a Gaussian mixture model on the real line with a subgaussian mixing distribution. Leveraging complex-analytic techniques, we show that with high probability the NPMLE based on a sample of size $n$ has $O(\log n)$ atoms (mass points), significantly improving the deterministic upper bound of $n$ due to Lindsay \cite{lindsay1983geometry1}. Notably, any such Gaussian mixture is statistically indistinguishable from a finite one with $O(\log n)$ components (and this is tight for certain mixtures). Thus, absent any explicit form of model selection, NPMLE automatically chooses the right model complexity, a property we term \emph{self-regularization}. Extensions to other exponential families are given. As a statistical application, we show that this structural property can be harnessed to bootstrap existing Hellinger risk bound of the (parametric) MLE for finite Gaussian mixtures to the NPMLE for general Gaussian mixtures, recovering a result of Zhang \cite{zhang2009generalized}.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Spin torque gate magnetic field sensor

Spin-orbit torque provides an efficient pathway to manipulate the magnetic state and magnetization dynamics of magnetic materials, which is crucial for energy-efficient operation of a variety of spintronic devices such as magnetic memory, logic, oscillator, and neuromorphic computing. Here, we describe and experimentally demonstrate a strategy for the realization of a spin torque gate magnetic field sensor with extremely simple structure by exploiting the longitudinal field dependence of the spin torque driven magnetization switching. Unlike most magnetoresistance sensors which require a delicate magnetic bias to achieve a linear response to the external field, the spin torque gate sensor can achieve the same without any magnetic bias, which greatly simplifies the sensor structure. Furthermore, by driving the sensor using an ac current, the dc offset is automatically suppressed, which eliminates the need for a bridge or compensation circuit. We verify the concept using the newly developed WTe2/Ti/CoFeB trilayer and demonstrate that the sensor can work linearly in the range of 3-10 Oe with negligible dc offset.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Terahertz Emission From an Exchange-Coupled Synthetic Antiferromagnet

We report on terahertz emission from FeMnPt/Ru/FeMnPt and Pt/CoFeB/Ru/CoFeB/Pt synthetic antiferromagnet (SAF) structures upon irradiation by a femtosecond laser; the former is via the anomalous Hall effect, whereas the latter is through the inverse spin Hall effect. The antiparallel alignment of the two ferromagnetic layers leads to a terahertz emission peak amplitude that is almost double that for a corresponding single-layer or bilayer emitter with the same equivalent thickness. In addition, we demonstrate by both simulation and experiment that terahertz emission provides a powerful tool to probe the magnetization reversal processes of individual ferromagnetic layers in a SAF structure, as the terahertz signal is proportional to the vector difference of the magnetizations of the two ferromagnetic layers.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Intrinsic skyrmions in monolayer Janus magnets

Skyrmions are localized solitonic spin textures with protected topology, which are promising as information carriers in ultra-dense and energy-efficient logic and memory devices. Recently, magnetic skyrmions have been observed in magnetic thin films, and are stabilized by the extrinsic interfacial Dzyaloshinskii-Moriya interaction (DMI) and/or external magnetic fields. The specific effects in magnetic monolayer materials have not been thoroughly studied. Here, we investigate the intrinsic magnetic skyrmions in a family of monolayer Janus van der Waals magnets, MnSTe, MnSeTe, VSeTe, and MnSSe, by the first-principles calculations combined with the micromagnetic simulations. The monolayer Janus MnSTe, MnSeTe, and VSeTe with out-of-plane geometric asymmetry and strong spin-orbit coupling (SOC) have a large intrinsic DMI, which could stabilize a sub-50 nm intrinsic skyrmions in monolayer MnSTe and MnSeTe at zero magnetic field. While monolayer VSeTe with in-plane easy axis forms magnetic domain rather than skyrmions. Moreover, the size and shape of skyrmions can be tuned by an external magnetic field. Therefore, our work motivates a new vista for seeking intrinsic skyrmions in atomic-scale magnets.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Spin Hall magnetoresistance sensor using Au$_x$Pt$_{1-x}$ as the spin-orbit torque biasing layer

We report on investigation of spin Hall magnetoresistance sensor based on NiFe/AuxPt1-x bilayers. Compared to NiFe/Pt, the NiFe/AuxPt1-x sensor exhibits a much lower power consumption (reduced by about 57%), due to 80% enhancement of spin-orbit torque efficiency of AuxPt1-x at an optimum composition of x = 0.19 as compared to pure Pt. The enhanced spin-orbit torque efficiency allows to increase the thickness of NiFe from 1.8 nm to 2.5 nm without significantly increasing the power consumption. We show that, by increasing the NiFe thickness, we were able to improve the working field range (0.86 Oe), operation temperature range (150 degree C) and detectivity (0.71 nT/sqrt(Hz) at 1 Hz) of the sensor, which is important for practical applications.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Terahertz emission from anomalous Hall effect in a single-layer ferromagnet

We report on terahertz emission from a single layer ferromagnet which involves the generation of backflow nonthermal charge current from the ferromagnet/dielectric interface by femtosecond laser excitation and subsequent conversion of the charge current to a transverse transient charge current via the anomalous Hall effect, thereby generating the THz radiation. The THz emission can be either enhanced or suppressed, or even the polarity can be reversed, by introducing a magnetization gradient in the thickness direction of the ferromagnet. Unlike spintronic THz emitters reported previously, it does not require additional non-magnetic layer or Rashba interface.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

The binary symmetric stochastic block model deals with a random graph of $n$ vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability $p$ within clusters and $q$ across clusters. In the asymptotic regime of $p=a \log n/n$ and $q=b \log n/n$ for fixed $a,b$ and $n \to \infty$, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. \cite{Abbe14}. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to $n$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions

Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model of two equal-sized clusters. The same was shown for the case of a single cluster and outliers. Extending the proof techniques, in this paper it is shown that SDP relaxations also achieve the sharp recovery threshold in the following cases: (1) Binary stochastic block model with two clusters of sizes proportional to network size but not necessarily equal; (2) Stochastic block model with a fixed number of equal-sized clusters; (3) Binary censored block model with the background graph being Erdős-Rényi. Furthermore, a sufficient condition is given for an SDP procedure to achieve exact recovery for the general case of a fixed number of clusters plus outliers. These results demonstrate the versatility of SDP relaxation as a simple, general purpose, computationally feasible methodology for community detection.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Chebyshev polynomials, moment matching, and optimal estimation of the unseen

We consider the problem of estimating the support size of a discrete distribution whose minimum non-zero mass is at least $ \frac{1}{k}$. Under the independent sampling model, we show that the sample complexity, i.e., the minimal sample size to achieve an additive error of $εk$ with probability at least 0.1 is within universal constant factors of $ \frac{k}{\log k}\log^2\frac{1}ε $, which improves the state-of-the-art result of $ \frac{k}{ε^2 \log k} $ in \cite{VV13}. Similar characterization of the minimax risk is also obtained. Our procedure is a linear estimator based on the Chebyshev polynomial and its approximation-theoretic properties, which can be evaluated in $O(n+\log^2 k)$ time and attains the sample complexity within a factor of six asymptotically. The superiority of the proposed estimator in terms of accuracy, computational efficiency and scalability is demonstrated in a variety of synthetic and real datasets.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Equivalence of additive-combinatorial linear inequalities for Shannon entropy and differential entropy

This paper addresses the correspondence between linear inequalities of Shannon entropy and differential entropy for sums of independent group-valued random variables. We show that any balanced (with the sum of coefficients being zero) linear inequality of Shannon entropy holds if and only if its differential entropy counterpart also holds; moreover, any linear inequality for differential entropy must be balanced. In particular, our result shows that recently proved differential entropy inequalities by Kontoyiannis and Madiman \cite{KM14} can be deduced from their discrete counterparts due to Tao \cite{Tao10} in a unified manner. Generalizations to certain abelian groups are also obtained. Our proof of extending inequalities of Shannon entropy to differential entropy relies on a result of Rényi \cite{Renyi59} which relates the Shannon entropy of a finely discretized random variable to its differential entropy and also helps in establishing the entropy of the sum of quantized random variables is asymptotically equal to that of the quantized sum; the converse uses the asymptotics of the differential entropy of convolutions with weak additive noise.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Estimating the number of unseen species: A bird in the hand is worth $\log n $ in the bush

Estimating the number of unseen species is an important problem in many scientific endeavors. Its most popular formulation, introduced by Fisher, uses $n$ samples to predict the number $U$ of hitherto unseen species that would be observed if $t\cdot n$ new samples were collected. Of considerable interest is the largest ratio $t$ between the number of new and existing samples for which $U$ can be accurately predicted. In seminal works, Good and Toulmin constructed an intriguing estimator that predicts $U$ for all $t\le 1$, thereby showing that the number of species can be estimated for a population twice as large as that observed. Subsequently Efron and Thisted obtained a modified estimator that empirically predicts $U$ even for some $t>1$, but without provable guarantees. We derive a class of estimators that $\textit{provably}$ predict $U$ not just for constant $t>1$, but all the way up to $t$ proportional to $\log n$. This shows that the number of species can be estimated for a population $\log n$ times larger than that observed, a factor that grows arbitrarily large as $n$ increases. We also show that this range is the best possible and that the estimators' mean-square error is optimal up to constants for any $t$. Our approach yields the first provable guarantee for the Efron-Thisted estimator and, in addition, a variant which achieves stronger theoretical and experimental performance than existing methodologies on a variety of synthetic and real datasets. The estimators we derive are simple linear estimators that are computable in time proportional to $n$. The performance guarantees hold uniformly for all distributions, and apply to all four standard sampling models commonly used across various scientific disciplines: multinomial, Poisson, hypergeometric, and Bernoulli product.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Information Limits for Recovering a Hidden Community

We study the problem of recovering a hidden community of cardinality $K$ from an $n \times n$ symmetric data matrix $A$, where for distinct indices $i,j$, $A_{ij} \sim P$ if $i, j$ both belong to the community and $A_{ij} \sim Q$ otherwise, for two known probability distributions $P$ and $Q$ depending on $n$. If $P={\rm Bern}(p)$ and $Q={\rm Bern}(q)$ with $p>q$, it reduces to the problem of finding a densely-connected $K$-subgraph planted in a large Erdös-Rényi graph; if $P=\mathcal{N}(μ,1)$ and $Q=\mathcal{N}(0,1)$ with $μ>0$, it corresponds to the problem of locating a $K \times K$ principal submatrix of elevated means in a large Gaussian random matrix. We focus on two types of asymptotic recovery guarantees as $n \to \infty$: (1) weak recovery: expected number of classification errors is $o(K)$; (2) exact recovery: probability of classifying all indices correctly converges to one. Under mild assumptions on $P$ and $Q$, and allowing the community size to scale sublinearly with $n$, we derive a set of sufficient conditions and a set of necessary conditions for recovery, which are asymptotically tight with sharp constants. The results hold in particular for the Gaussian case, and for the case of bounded log likelihood ratio, including the Bernoulli case whenever $\frac{p}{q}$ and $\frac{1-p}{1-q}$ are bounded away from zero and infinity. An important algorithmic implication is that, whenever exact recovery is information theoretically possible, any algorithm that provides weak recovery when the community size is concentrated near $K$ can be upgraded to achieve exact recovery in linear additional time by a simple voting procedure.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Interstellar Pickup Ion Production in the Global Heliosphere and Heliosheath

Interstellar Pickup ions (PUIs) play a significant part in mediating the solar wind (SW) interaction with the interstellar medium. In this paper, we examine the details of spatial variation of the PUI velocity distribution function (VDF) in the SW by solving the PUI transport equation. We assume the PUI distribution is isotropic resulting from strong pitch-angle scattering by wave-particle interaction. A three-dimensional model combining the MHD treatment of the background SW and neutrals with a kinetic treatment of PUIs throughout the heliosphere and the surrounding local interstellar medium (LISM) has been developed. The model generates PUI power law tails via second-order Fermi process. We analyze how PUIs transform across the heliospheric termination shock (TS) and obtain the PUI phase space distribution in the inner heliosheath including continuing velocity diffusion. Our simulated PUI spectra are compared with observations made by New Horizons, Ulysses, Voyager 1, 2 and Cassini, and a satisfactory agreement is demonstrated. Some specific features in the observations, for example, a cutoff of PUI VDF at $v = V_{SW}$ and a $f \propto v^{-5}$ tail in the reference frame of the SW, are well represented by the model.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Minimax rates of entropy estimation on large alphabets via best polynomial approximation

Consider the problem of estimating the Shannon entropy of a distribution over $k$ elements from $n$ independent samples. We show that the minimax mean-square error is within universal multiplicative constant factors of $$\Big(\frac{k }{n \log k}\Big)^2 + \frac{\log^2 k}{n}$$ if $n$ exceeds a constant factor of $\frac{k}{\log k}$; otherwise there exists no consistent estimator. This refines the recent result of Valiant-Valiant \cite{VV11} that the minimal sample size for consistent entropy estimation scales according to $Θ(\frac{k}{\log k})$. The apparatus of best polynomial approximation plays a key role in both the construction of optimal estimators and, via a duality argument, the minimax lower bound.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Near Optimal Compressed Sensing of a Class of Sparse Low-Rank Matrices via Sparse Power Factorization

Compressed sensing of simultaneously sparse and low-rank matrices enables recovery of sparse signals from a few linear measurements of their bilinear form. One important question is how many measurements are needed for a stable reconstruction in the presence of measurement noise. Unlike conventional compressed sensing for sparse vectors, where convex relaxation via the $\ell_1$-norm achieves near optimal performance, for compressed sensing of sparse low-rank matrices, it has been shown recently Oymak et al. that convex programmings using the nuclear norm and the mixed norm are highly suboptimal even in the noise-free scenario. We propose an alternating minimization algorithm called sparse power factorization (SPF) for compressed sensing of sparse rank-one matrices. For a class of signals whose sparse representation coefficients are fast-decaying, SPF achieves stable recovery of the rank-1 matrix formed by their outer product and requires number of measurements within a logarithmic factor of the information-theoretic fundamental limit. For the recovery of general sparse low-rank matrices, we propose subspace-concatenated SPF (SCSPF), which has analogous near optimal performance guarantees to SPF in the rank-1 case. Numerical results show that SPF and SCSPF empirically outperform convex programmings using the best known combinations of mixed norm and nuclear norm.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices

This paper considers sparse spiked covariance matrix models in the high-dimensional setting and studies the minimax estimation of the covariance matrix and the principal subspace as well as the minimax rank detection. The optimal rate of convergence for estimating the spiked covariance matrix under the spectral norm is established, which requires significantly different techniques from those for estimating other structured covariance matrices such as bandable or sparse covariance matrices. We also establish the minimax rate under the spectral norm for estimating the principal subspace, the primary object of interest in principal component analysis. In addition, the optimal rate for the rank detection boundary is obtained. This result also resolves the gap in a recent paper by Berthet and Rigollet [1] where the special case of rank one is considered.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Self-current induced spin-orbit torque in FeMn/Pt multilayers

Extensive efforts have been devoted to the study of spin-orbit torque in ferromagnetic metal/heavy metal bilayers and exploitation of it for magnetization switching using an in-plane current. As the spin-orbit torque is inversely proportional to the thickness of the ferromagnetic layer, sizable effect has only been realized in bilayers with an ultrathin ferromagnetic layer. Here we demonstrate that, by stacking ultrathin Pt and FeMn alternately, both ferromagnetic properties and current induced spin-orbit torque can be achieved in FeMn/Pt multilayers without any constraint on its total thickness. The critical behavior of these multilayers follows closely three-dimensional Heisenberg model with a finite Curie temperature distribution. The spin torque effective field is about 4 times larger than that of NiFe/Pt bilayer with a same equivalent NiFe thickness. The self-current generated spin torque is able to switch the magnetization reversibly without the need for an external field or a thick heavy metal layer. The removal of both thickness constraint and necessity of using an adjacent heavy metal layer opens new possibilities for exploiting spin-orbit torque for practical applications.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Semidefinite Programs for Exact Recovery of a Hidden Community

We study a semidefinite programming (SDP) relaxation of the maximum likelihood estimation for exactly recovering a hidden community of cardinality $K$ from an $n \times n$ symmetric data matrix $A$, where for distinct indices $i,j$, $A_{ij} \sim P$ if $i, j$ are both in the community and $A_{ij} \sim Q$ otherwise, for two known probability distributions $P$ and $Q$. We identify a sufficient condition and a necessary condition for the success of SDP for the general model. For both the Bernoulli case ($P={\rm Bern}(p)$ and $Q={\rm Bern}(q)$ with $p>q$) and the Gaussian case ($P=\mathcal{N}(μ,1)$ and $Q=\mathcal{N}(0,1)$ with $μ>0$), which correspond to the problem of planted dense subgraph recovery and submatrix localization respectively, the general results lead to the following findings: (1) If $K=ω( n /\log n)$, SDP attains the information-theoretic recovery limits with sharp constants; (2) If $K=Θ(n/\log n)$, SDP is order-wise optimal, but strictly suboptimal by a constant factor; (3) If $K=o(n/\log n)$ and $K \to \infty$, SDP is order-wise suboptimal. The same critical scaling for $K$ is found to hold, up to constant factors, for the performance of SDP on the stochastic block model of $n$ vertices partitioned into multiple communities of equal size $K$. A key ingredient in the proof of the necessary condition is a construction of a primal feasible solution based on random perturbation of the true cluster matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Strong data-processing inequalities for channels and Bayesian networks

The data-processing inequality, that is, $I(U;Y) \le I(U;X)$ for a Markov chain $U \to X \to Y$, has been the method of choice for proving impossibility (converse) results in information theory and many other disciplines. Various channel-dependent improvements (called strong data-processing inequalities, or SDPIs) of this inequality have been proposed both classically and more recently. In this note we first survey known results relating various notions of contraction for a single channel. Then we consider the basic extension: given SDPI for each constituent channel in a Bayesian network, how to produce an end-to-end SDPI? Our approach is based on the (extract of the) Evans-Schulman method, which is demonstrated for three different kinds of SDPIs, namely, the usual Ahslwede-Gács type contraction coefficients (mutual information), Dobrushin's contraction coefficients (total variation), and finally the $F_I$-curve (the best possible non-linear SDPI for a given channel). Resulting bounds on the contraction coefficients are interpreted as probability of site percolation. As an example, we demonstrate how to obtain SDPI for an $n$-letter memoryless channel with feedback given an SDPI for $n=1$. Finally, we discuss a simple observation on the equivalence of a linear SDPI and comparison to an erasure channel (in the sense of "less noisy" order). This leads to a simple proof of a curious inequality of Samorodnitsky (2015), and sheds light on how information spreads in the subsets of inputs of a memoryless channel.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Thickness dependence of spin Hall magnetoresistance in FeMn/Pt bilayers

We investigated spin Hall magnetoresistance in FeMn/Pt bilayers, which was found to be one order of magnitude larger than that of heavy metal and insulating ferromagnet or antiferromagnet bilayer systems, and comparable to that of NiFe/Pt bilayers. The spin Hall magnetoresistance shows a non-monotonic dependence on the thicknesses of both FeMn and Pt. The former can be accounted for by the thickness dependence of net magnetization in FeMn thin films, whereas the latter is mainly due to spin accumulation and diffusion in Pt. Through analysis of the Pt thickness dependence, the spin Hall angle, spin diffusion length of Pt and the real part of spin mixing conductance were determined to be 0.2, 1.1 nm, and $5.5 * 10^{14} Ω^{-1} m^{-2}$, respectively. The results corroborate the spin orbit torque effect observed in this system recently.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Wasserstein continuity of entropy and outer bounds for interference channels

It is shown that under suitable regularity conditions, differential entropy is a Lipschitz functional on the space of distributions on $n$-dimensional Euclidean space with respect to the quadratic Wasserstein distance. Under similar conditions, (discrete) Shannon entropy is shown to be Lipschitz continuous in distributions over the product space with respect to Ornstein's $\bar d$-distance (Wasserstein distance corresponding to the Hamming distance). These results together with Talagrand's and Marton's transportation-information inequalities allow one to replace the unknown multi-user interference with its i.i.d. approximations. As an application, a new outer bound for the two-user Gaussian interference channel is proved, which, in particular, settles the "missing corner point" problem of Costa (1985).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Computational barriers in minimax submatrix detection

This paper studies the minimax detection of a small submatrix of elevated mean in a large matrix contaminated by additive Gaussian noise. To investigate the tradeoff between statistical performance and computational cost from a complexity-theoretic perspective, we consider a sequence of discretized models which are asymptotically equivalent to the Gaussian model. Under the hypothesis that the planted clique detection problem cannot be solved in randomized polynomial time when the clique size is of smaller order than the square root of the graph size, the following phase transition phenomenon is established: when the size of the large matrix $p\to\infty$, if the submatrix size $k=Θ(p^α)$ for any $α\in(0,{2}/{3})$, computational complexity constraints can incur a severe penalty on the statistical performance in the sense that any randomized polynomial-time test is minimax suboptimal by a polynomial factor in $p$; if $k=Θ(p^α)$ for any $α\in({2}/{3},1)$, minimax optimal detection can be attained within constant factors in linear time. Using Schatten norm loss as a representative example, we show that the hardness of attaining the minimax estimation rate can crucially depend on the loss function. Implications on the hardness of support recovery are also obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Computational Lower Bounds for Community Detection on Random Graphs

This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi random graph $\mathcal{G}(N,q)$, where the edge probability within the community exceeds $q$ by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computational complexity of detecting the community exhibits the following phase transition phenomenon: As the graph size $N$ grows and the graph becomes sparser according to $q=N^{-α}$, there exists a critical value of $α= \frac{2}{3}$, below which there exists a computationally intensive procedure that can detect far smaller communities than any computationally efficient procedure, and above which a linear-time procedure is statistically optimal. The results also lead to the average-case hardness results for recovering the dense community and approximating the densest $K$-subgraph.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Dissipation of information in channels with input constraints

One of the basic tenets in information theory, the data processing inequality states that output divergence does not exceed the input divergence for any channel. For channels without input constraints, various estimates on the amount of such contraction are known, Dobrushin's coefficient for the total variation being perhaps the most well-known. This work investigates channels with average input cost constraint. It is found that while the contraction coefficient typically equals one (no contraction), the information nevertheless dissipates. A certain non-linear function, the \emph{Dobrushin curve} of the channel, is proposed to quantify the amount of dissipation. Tools for evaluating the Dobrushin curve of additive-noise channels are developed based on coupling arguments. Some basic applications in stochastic control, uniqueness of Gibbs measures and fundamental limits of noisy circuits are discussed. As an application, it shown that in the chain of $n$ power-constrained relays and Gaussian channels the end-to-end mutual information and maximal squared correlation decay as $Θ(\frac{\log\log n}{\log n})$, which is in stark contrast with the exponential decay in chains of discrete channels. Similarly, the behavior of noisy circuits (composed of gates with bounded fan-in) and broadcasting of information on trees (of bounded degree) does not experience threshold behavior in the signal-to-noise ratio (SNR). Namely, unlike the case of discrete channels, the probability of bit error stays bounded away from $1\over 2$ regardless of the SNR.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Electrical Oscillation in Pt/VO2 Bilayer Strips

We report on the observation of stable electrical oscillation in Pt/VO2 bilayer strips, in which the Pt overlayer serves the dual purposes of heating up the VO2 and weakening the electric field in the VO2 layer. Systematic measurements in an ultrahigh vacuum nanoprobe system show that the oscillation frequency increases with the bias current and/or with decreasing device dimension. In contrast to most VO2-based oscillators reported to date, which are electrically triggered, current-induced Joule heating in the Pt overlayer is found to play a dominant role in the generation of oscillation in Pt/VO2 bilayers. A simple model involving thermally triggered transition of VO2 on a heat sink is able to account for the experimental observations. The results in this work provide an alternative view of the triggering mechanism in VO2-based oscillators.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Submatrix localization via message passing

The principal submatrix localization problem deals with recovering a $K\times K$ principal submatrix of elevated mean $μ$ in a large $n\times n$ symmetric matrix subject to additive standard Gaussian noise. This problem serves as a prototypical example for community detection, in which the community corresponds to the support of the submatrix. The main result of this paper is that in the regime $Ω(\sqrt{n}) \leq K \leq o(n)$, the support of the submatrix can be weakly recovered (with $o(K)$ misclassification errors on average) by an optimized message passing algorithm if $λ= μ^2K^2/n$, the signal-to-noise ratio, exceeds $1/e$. This extends a result by Deshpande and Montanari previously obtained for $K=Θ(\sqrt{n}).$ In addition, the algorithm can be extended to provide exact recovery whenever information-theoretically possible and achieve the information limit of exact recovery as long as $K \geq \frac{n}{\log n} (\frac{1}{8e} + o(1))$. The total running time of the algorithm is $O(n^2\log n)$. Another version of the submatrix localization problem, known as noisy biclustering, aims to recover a $K_1\times K_2$ submatrix of elevated mean $μ$ in a large $n_1\times n_2$ Gaussian matrix. The optimized message passing algorithm and its analysis are adapted to the bicluster problem assuming $Ω(\sqrt{n_i}) \leq K_i \leq o(n_i)$ and $K_1\asymp K_2.$ A sharp information-theoretic condition for the weak recovery of both clusters is also identified.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Peak-to-average power ratio of good codes for Gaussian channel

Consider a problem of forward error-correction for the additive white Gaussian noise (AWGN) channel. For finite blocklength codes the backoff from the channel capacity is inversely proportional to the square root of the blocklength. In this paper it is shown that codes achieving this tradeoff must necessarily have peak-to-average power ratio (PAPR) proportional to logarithm of the blocklength. This is extended to codes approaching capacity slower, and to PAPR measured at the output of an OFDM modulator. As a by-product the convergence of (Smith's) amplitude-constrained AWGN capacity to Shannon's classical formula is characterized in the regime of large amplitudes. This converse-type result builds upon recent contributions in the study of empirical output distributions of good channel codes.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Sparse PCA: Optimal rates and adaptive estimation

Principal component analysis (PCA) is one of the most commonly used statistical procedures with a wide range of applications. This paper considers both minimax and adaptive estimation of the principal subspace in the high dimensional setting. Under mild technical conditions, we first establish the optimal rates of convergence for estimating the principal subspace which are sharp with respect to all the parameters, thus providing a complete characterization of the difficulty of the estimation problem in term of the convergence rate. The lower bound is obtained by calculating the local metric entropy and an application of Fano's lemma. The rate optimal estimator is constructed using aggregation, which, however, might not be computationally feasible. We then introduce an adaptive procedure for estimating the principal subspace which is fully data driven and can be computed efficiently. It is shown that the estimator attains the optimal rates of convergence simultaneously over a large collection of the parameter spaces. A key idea in our construction is a reduction scheme which reduces the sparse PCA problem to a high-dimensional multivariate regression problem. This method is potentially also useful for other related problems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Investigation of Magnetic Proximity Effect inTa/YIG Bilayer Hall Bar Structure

In this work, the investigation of magnetic proximity effect was extended to Ta which has been reported to have a negative spin Hall angle. Magnetoresistance and Hall measurements for in-plane and out-of-plane applied magnetic field sweeps were carried out at room temperature. The size of the MR ratio observed (~10-5) and its magnetization direction dependence are similar to that reported in Pt/YIG, both of which can be explained by the spin Hall magnetoresistance theory. Additionally, a flip of magnetoresistance polarity is observed at 4 K in the temperature dependent measurements, which can be explained by the magnetic proximity effect induced anisotropic magnetoresistance at low temperature. Our findings suggest that both magnetic proximity effect and spin Hall magnetoresistance have contribution to the recently observed unconventional magnetoresistance effect.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Local Electron Field Emission Study of Two-dimensional Carbon

A systematic field-emission study has been carried out on different types of two-dimensional carbons in ultrahigh vacuum with the cathode-anode distance ranging from near-contact to about 124 nm. An analytical model has been developed to explain the increase of field enhancement factor with the cathode-anode distance. Good agreement has been achieved between the calculation results and experimental data, including those reported in literature. The work provides useful insights into the characteristics of field emission from two-dimensional carbon.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Search for carbon stars and DZ white dwarfs in SDSS spectra survey through machine learning

Carbon stars and DZ white dwarfs are two types of rare objects in the Galaxy. In this paper, we have applied the label propagation algorithm to search for these two types of stars from Data Release Eight (DR8) of the Sloan Digital Sky Survey (SDSS), which is verified to be efficient by calculating precision and recall. From nearly two million spectra including stars, galaxies and QSOs, we have found 260 new carbon stars in which 96 stars have been identified as dwarfs and 7 identified as giants, and 11 composition spectrum systems (each of them consists of a white dwarf and a carbon star). Similarly, using the label propagation method, we have obtained 29 new DZ white dwarfs from SDSS DR8. Compared with PCA reconstructed spectra, the 29 findings are typical DZ white dwarfs. We have also investigated their proper motions by comparing them with proper motion distribution of 9,374 white dwarfs, and found that they satisfy the current observed white dwarfs by SDSS generally have large proper motions. In addition, we have estimated their effective temperatures by fitting the polynomial relationship between effective temperature and g-r color of known DZ white dwarfs, and found 12 of the 29 new DZ white dwarfs are cool, in which nine are between 6000K and 6600K, and three are below 6000K.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Tight Lower Bound for Linear Sketches of Moments

The problem of estimating frequency moments of a data stream has attracted a lot of attention since the onset of streaming algorithms [AMS99]. While the space complexity for approximately computing the $p^{\rm th}$ moment, for $p\in(0,2]$ has been settled [KNW10], for $p>2$ the exact complexity remains open. For $p>2$ the current best algorithm uses $O(n^{1-2/p}\log n)$ words of space [AKO11,BO10], whereas the lower bound is of $Ω(n^{1-2/p})$ [BJKS04]. In this paper, we show a tight lower bound of $Ω(n^{1-2/p}\log n)$ words for the class of algorithms based on linear sketches, which store only a sketch $Ax$ of input vector $x$ and some (possibly randomized) matrix $A$. We note that all known algorithms for this problem are linear sketches.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Volume Ratio, Sparsity, and Minimaxity under Unitarily Invariant Norms

The current paper presents a novel machinery for studying non-asymptotic minimax estimation of high-dimensional matrices, which yields tight minimax rates for a large collection of loss functions in a variety of problems. Based on the convex geometry of finite-dimensional Banach spaces, we first develop a volume ratio approach for determining minimax estimation rates of unconstrained normal mean matrices under all squared unitarily invariant norm losses. In addition, we establish the minimax rates for estimating mean matrices with submatrix sparsity, where the sparsity constraint introduces an additional term in the rate whose dependence on the norm differs completely from the rate of the unconstrained problem. Moreover, the approach is applicable to the matrix completion problem under the low-rank constraint. The new method also extends beyond the normal mean model. In particular, it yields tight rates in covariance matrix estimation and Poisson rate matrix estimation problems for all unitarily invariant norms.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Electrical transport across metal/two-dimensional carbon junctions: Edge versus side contacts

Metal/two-dimensional carbon junctions are characterized by using a nanoprobe in an ultrahigh vacuum environment. Significant differences were found in bias voltage (V) dependence of differential conductance (dI/dV) between edge- and side-contact; the former exhibits a clear linear relationship (i.e., dI/dV \propto V), whereas the latter is characterized by a nonlinear dependence, dI/dV \propto V3/2. Theoretical calculations confirm the experimental results, which are due to the robust two-dimensional nature of the carbon materials under study. Our work demonstrates the importance of contact geometry in graphene-based electronic devices.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimal Detection For Sparse Mixtures

Detection of sparse signals arises in a wide range of modern scientific studies. The focus so far has been mainly on Gaussian mixture models. In this paper, we consider the detection problem under a general sparse mixture model and obtain an explicit expression for the detection boundary. It is shown that the fundamental limits of detection is governed by the behavior of the log-likelihood ratio evaluated at an appropriate quantile of the null distribution. We also establish the adaptive optimality of the higher criticism procedure across all sparse mixtures satisfying certain mild regularity conditions. In particular, the general results obtained in this paper recover and extend in a unified manner the previously known results on sparse detection far beyond the conventional Gaussian model and other exponential families.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimal Phase Transitions in Compressed Sensing

Compressed sensing deals with efficient recovery of analog signals from linear encodings. This paper presents a statistical study of compressed sensing by modeling the input signal as an i.i.d. process with known distribution. Three classes of encoders are considered, namely optimal nonlinear, optimal linear and random linear encoders. Focusing on optimal decoders, we investigate the fundamental tradeoff between measurement rate and reconstruction fidelity gauged by error probability and noise sensitivity in the absence and presence of measurement noise, respectively. The optimal phase transition threshold is determined as a functional of the input distribution and compared to suboptimal thresholds achieved by popular reconstruction algorithms. In particular, we show that Gaussian sensing matrices incur no penalty on the phase transition threshold with respect to optimal nonlinear encoding. Our results also provide a rigorous justification of previous results based on replica heuristics in the weak-noise regime.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Bandgap engineering of zigzag graphene nanoribbons by manipulating edge states via defective boundaries

One of severe limits of graphene nanoribbons (GNRs) in future applications is that zigzag GNRs (ZGNRs) are gapless, so cannot be used in field effect transistors (FETs). In this paper, using tight-binding approach and first principles method, we derived and proved a general edge (boundary) condition for the opening of a significant bandgap in ZGNRs with defective edge structures. The proposed semiconducting GNRs have some interesting properties including the one that they can be embedded and integrated in a large piece of graphene without the need of completely cutting them out. We also demonstrated a new type of high-performance all-ZGNR FET.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Hysteresis of Electronic Transport in Graphene Transistors

Graphene field effect transistors commonly comprise graphene flakes lying on SiO2 surfaces. The gate-voltage dependent conductance shows hysteresis depending on the gate sweeping rate/range. It is shown here that the transistors exhibit two different kinds of hysteresis in their electrical characteristics. Charge transfer causes a positive shift in the gate voltage of the minimum conductance, while capacitive gating can cause the negative shift of conductance with respect to gate voltage. The positive hysteretic phenomena decay with an increase of the number of layers in graphene flakes. Self-heating in helium atmosphere significantly removes adsorbates and reduces positive hysteresis. We also observed negative hysteresis in graphene devices at low temperature. It is also found that an ice layer on/under graphene has much stronger dipole moment than a water layer does. Mobile ions in the electrolyte gate and a polarity switch in the ferroelectric gate could also cause negative hysteresis in graphene transistors. These findings improved our understanding of the electrical response of graphene to its surroundings. The unique sensitivity to environment and related phenomena in graphene deserve further studies on nonvolatile memory, electrostatic detection and chemically driven applications.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Estimation in Gaussian Noise: Properties of the Minimum Mean-Square Error

Consider the minimum mean-square error (MMSE) of estimating an arbitrary random variable from its observation contaminated by Gaussian noise. The MMSE can be regarded as a function of the signal-to-noise ratio (SNR) as well as a functional of the input distribution (of the random variable to be estimated). It is shown that the MMSE is concave in the input distribution at any given SNR. For a given input distribution, the MMSE is found to be infinitely differentiable at all positive SNR, and in fact a real analytic function in SNR under mild conditions. The key to these regularity results is that the posterior distribution conditioned on the observation through Gaussian channels always decays at least as quickly as some Gaussian density. Furthermore, simple expressions for the first three derivatives of the MMSE with respect to the SNR are obtained. It is also shown that, as functions of the SNR, the curves for the MMSE of a Gaussian input and that of a non-Gaussian input cross at most once over all SNRs. These properties lead to simple proofs of the facts that Gaussian inputs achieve both the secrecy capacity of scalar Gaussian wiretap channels and the capacity of scalar Gaussian broadcast channels, as well as a simple proof of the entropy power inequality in the special case where one of the variables is Gaussian.

0 citations0 reviewsNo code linkedOpen access