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

Yajun Wang

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

ResearcherUnclaimed source record
Data Structures and Algorithmseess.SPSocial and Information NetworksComputer Science and Game TheoryDiscrete MathematicsMachine LearningComputer VisionInformation Retrievalmath.DSmath.NAmath.PRNumerical Analysisphysics.soc-phquant-phRobotics

Catalog footprint

What is connected

17works
15topics
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

17 published item(s)

preprint2024arXiv

Regularized coupling multiscale method for thermomechanical coupled problems

The coupling effects in multiphysics processes are often neglected in designing multiscale methods. The coupling may be described by a non-positive definite operator, which in turn brings significant challenges in multiscale simulations. In the paper, we develop a regularized coupling multiscale method based on the generalized multiscale finite element method (GMsFEM) to solve coupled thermomechanical problems, and it is referred to as the coupling generalized multiscale finite element method (CGMsFEM). The method consists of defining the coupling multiscale basis functions through local regularized coupling spectral problems in each coarse-grid block, which can be implemented by a novel design of two relaxation parameters. Compared to the standard GMsFEM, the proposed method can not only accurately capture the multiscale coupling correlation effects of multiphysics problems but also greatly improve computational efficiency with fewer multiscale basis functions. In addition, the convergence analysis is also established, and the optimal error estimates are derived, where the upper bound of errors is independent of the magnitude of the relaxation coefficient. Several numerical examples for periodic, random microstructure, and random material coefficients are presented to validate the theoretical analysis. The numerical results show that the CGMsFEM shows better robustness and efficiency than uncoupled GMsFEM.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Deterministic and universal quantum squeezing gate in virtue of teleportation-like protocol

Squeezing transformation as an essential component, gives rise to the possibility to perform various tasks of quantum information processing. However, the reported squeezing gate with best performance so far is a conditional realization at the expense of low success probability, while the performance of the deterministic ones is currently circumscribed by the limited squeezing degree of the non-classical ancilla. To address this issue, we develop and demonstrate a new scheme of deterministic and universal quantum squeezing gate with the property of non-local operation attributed to the teleportation-like protocol. We demonstrate high fidelity squeezing operation, even when the level of target squeezing being up to 10 dB, where a squeezed state with non-classical noise reduction of 6.5 dB is directly observed. Moreover, we perform a high-fidelity complex operation including a Fourier transformation and a phase squeezing gate, exploring the potential of implementing the complex task of quantum information processing with the presented functional unit. Our method can be applied to distributed quantum processor, the creation of exotic non-classical states, and quantum error correction.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

NGAME: Negative Mining-aware Mini-batching for Extreme Classification

Extreme Classification (XC) seeks to tag data points with the most relevant subset of labels from an extremely large label set. Performing deep XC with dense, learnt representations for data points and labels has attracted much attention due to its superiority over earlier XC methods that used sparse, hand-crafted features. Negative mining techniques have emerged as a critical component of all deep XC methods that allow them to scale to millions of labels. However, despite recent advances, training deep XC models with large encoder architectures such as transformers remains challenging. This paper identifies that memory overheads of popular negative mining techniques often force mini-batch sizes to remain small and slow training down. In response, this paper introduces NGAME, a light-weight mini-batch creation technique that offers provably accurate in-batch negative samples. This allows training with larger mini-batches offering significantly faster convergence and higher accuracies than existing negative sampling techniques. NGAME was found to be up to 16% more accurate than state-of-the-art methods on a wide array of benchmark datasets for extreme classification, as well as 3% more accurate at retrieving search engine queries in response to a user webpage visit to show personalized ads. In live A/B tests on a popular search engine, NGAME yielded up to 23% gains in click-through-rates.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A PAPR Reduction Method Based on Artificial Bee Colony Algorithm for OFDM Signals

One of the major drawbacks of orthogonal frequency division multiplexing (OFDM) signals is the high peak to average power ratio (PAPR) of the transmitted signal. Many PAPR reduction techniques have been proposed in the literature, among which, partial transmit sequence (PTS) technique has been taken considerable investigation.However, PTS technique requires an exhaustive search over all combinations of allowed phase factors, whose complexity increases exponentially with the number of sub-blocks. In this paper, a newly suboptimal method based on modified artificial bee colony (ABC-PTS) algorithm is proposed to search the better combination of phase factors. The ABC-PTS algorithm can significantly reduce the computational complexity for larger PTS subblocks and offers lower PAPR at the same time. Simulation results show that the ABC-PTS algorithm is an efficient method to achieve significant PAPR reduction.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

DymSLAM:4D Dynamic Scene Reconstruction Based on Geometrical Motion Segmentation

Most SLAM algorithms are based on the assumption that the scene is static. However, in practice, most scenes are dynamic which usually contains moving objects, these methods are not suitable. In this paper, we introduce DymSLAM, a dynamic stereo visual SLAM system being capable of reconstructing a 4D (3D + time) dynamic scene with rigid moving objects. The only input of DymSLAM is stereo video, and its output includes a dense map of the static environment, 3D model of the moving objects and the trajectories of the camera and the moving objects. We at first detect and match the interesting points between successive frames by using traditional SLAM methods. Then the interesting points belonging to different motion models (including ego-motion and motion models of rigid moving objects) are segmented by a multi-model fitting approach. Based on the interesting points belonging to the ego-motion, we are able to estimate the trajectory of the camera and reconstruct the static background. The interesting points belonging to the motion models of rigid moving objects are then used to estimate their relative motion models to the camera and reconstruct the 3D models of the objects. We then transform the relative motion to the trajectories of the moving objects in the global reference frame. Finally, we then fuse the 3D models of the moving objects into the 3D map of the environment by considering their motion trajectories to obtain a 4D (3D+time) sequence. DymSLAM obtains information about the dynamic objects instead of ignoring them and is suitable for unknown rigid objects. Hence, the proposed system allows the robot to be employed for high-level tasks, such as obstacle avoidance for dynamic objects. We conducted experiments in a real-world environment where both the camera and the objects were moving in a wide range.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Genetic Algorithm Based Nearly Optimal Peak Reduction Tone Set Selection for Adaptive Amplitude Clipping PAPR Reduction

In tone reservation (TR) based OFDM systems, the peak to average power ratio (PAPR) reduction performance mainly depends on the selection of the peak reduction tone (PRT) set and the optimal target clipping level. Finding the optimal PRT set requires an exhaustive search of all combinations of possible PRT sets, which is a nondeterministic polynomial-time (NP-hard) problem, and this search is infeasible for the number of tones used in practical systems. The existing selection methods, such as the consecutive PRT set, equally spaced PRT set and random PRT set, perform poorly compared to the optimal PRT set or incur high computational complexity. In this paper, an efficient scheme based on genetic algorithm (GA) with lower computational complexity is proposed for searching a nearly optimal PRT set. While TR-based clipping is simple and attractive for practical implementation, determining the optimal target clipping level is difficult. To overcome this problem, we propose an adaptive clipping control algorithm.Simulation results show that our proposed algorithms efficiently obtain a nearly optimal PRT set and good PAPR reductions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

PAPR Reduction Method Based on Parametric Minimum Cross Entropy for OFDM Signals

The partial transmit sequence (PTS) technique has received much attention in reducing the high peak to average power ratio (PAPR) of orthogonal frequency division multiplexing (OFDM) signals. However, the PTS technique requires an exhaustive search of all combinations of the allowed phase factors, and the search complexity increases exponentially with the number of sub-blocks. In this paper, a novel method based on parametric minimum cross entropy (PMCE) is proposed to search the optimal combination of phase factors. The PMCE algorithm not only reduces the PAPR significantly, but also decreases the computational complexity. The simulation results show that it achieves more or less the same PAPR reduction as that of exhaustive search.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Real-Time Monitoring of Area Angles with Synchrophasor Measurements

This paper develops a comprehensive framework of Area Angle Monitoring (AAM) to monitor the stress of bulk power transfer across an area of a power transmission system in real-time. Area angle is calculated from synchrophasor measurements to provide alert to system operators if the area angle exceeds pre-defined thresholds. This paper proposes general methods to identify these warning and emergency thresholds, and tests a mitigation strategy to relieve the area stress when the area angle exceeds the threshold. In order to handle the limited coverage of synchrophasor measurements, this paper proposes methods to estimate phase angles for boundary buses without synchrophasor measurements, which extends the application of AAM. AAM is verified for a power transmission area in the Western Electricity Coordinating Council system with both simulated data and synchrophasor measurements recorded from real events. A utility deployment to test the framework for monitoring area angle with live-stream and recorded synchrophasor data is described.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms

We define a general framework for a large class of combinatorial multi-armed bandit (CMAB) problems, where subsets of base arms with unknown distributions form super arms. In each round, a super arm is played and the base arms contained in the super arm are played and their outcomes are observed. We further consider the extension in which more based arms could be probabilistically triggered based on the outcomes of already triggered arms. The reward of the super arm depends on the outcomes of all played arms, and it only needs to satisfy two mild assumptions, which allow a large class of nonlinear reward instances. We assume the availability of an offline (α,β)-approximation oracle that takes the means of the outcome distributions of arms and outputs a super arm that with probability β generates an α fraction of the optimal expected reward. The objective of an online learning algorithm for CMAB is to minimize (α,β)-approximation regret, which is the difference between the αβ fraction of the expected reward when always playing the optimal super arm, and the expected reward of playing super arms according to the algorithm. We provide CUCB algorithm that achieves O(log n) distribution-dependent regret, where n is the number of rounds played, and we further provide distribution-independent bounds for a large class of reward functions. Our regret analysis is tight in that it matches the bound of UCB1 algorithm (up to a constant factor) for the classical MAB problem, and it significantly improves the regret bound in a earlier paper on combinatorial bandits with linear rewards. We apply our CMAB framework to two new applications, probabilistic maximum coverage and social influence maximization, both having nonlinear reward structures. In particular, application to social influence maximization requires our extension on probabilistically triggered arms.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Matroid Online Bipartite Matching and Vertex Cover

The Adwords and Online Bipartite Matching problems have enjoyed a renewed attention over the past decade due to their connection to Internet advertising. Our community has contributed, among other things, new models (notably stochastic) and extensions to the classical formulations to address the issues that arise from practical needs. In this paper, we propose a new generalization based on matroids and show that many of the previous results extend to this more general setting. Because of the rich structures and expressive power of matroids, our new setting is potentially of interest both in theory and in practice. In the classical version of the problem, the offline side of a bipartite graph is known initially while vertices from the online side arrive one at a time along with their incident edges. The objective is to maintain a decent approximate matching from which no edge can be removed. Our generalization, called Matroid Online Bipartite Matching, additionally requires that the set of matched offline vertices be independent in a given matroid. In particular, the case of partition matroids corresponds to the natural scenario where each advertiser manages multiple ads with a fixed total budget. Our algorithms attain the same performance as the classical version of the problems considered, which are often provably the best possible. We present $1-1/e$-competitive algorithms for Matroid Online Bipartite Matching under the small bid assumption, as well as a $1-1/e$-competitive algorithm for Matroid Online Bipartite Matching in the random arrival model. A key technical ingredient of our results is a carefully designed primal-dual waterfilling procedure that accommodates for matroid constraints. This is inspired by the extension of our recent charging scheme for Online Bipartite Vertex Cover.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a Social Network

A topic propagating in a social network reaches its tipping point if the number of users discussing it in the network exceeds a critical threshold such that a wide cascade on the topic is likely to occur. In this paper, we consider the task of selecting initial seed users of a topic with minimum size so that with a guaranteed probability the number of users discussing the topic would reach a given threshold. We formulate the task as an optimization problem called seed minimization with probabilistic coverage guarantee (SM-PCG). This problem departs from the previous studies on social influence maximization or seed minimization because it considers influence coverage with probabilistic guarantees instead of guarantees on expected influence coverage. We show that the problem is not submodular, and thus is harder than previously studied problems based on submodular function optimization. We provide an approximation algorithm and show that it approximates the optimal solution with both a multiplicative ratio and an additive error. The multiplicative ratio is tight while the additive error would be small if influence coverage distributions of certain seed sets are well concentrated. For one-way bipartite graphs we analytically prove the concentration condition and obtain an approximation algorithm with an $O(\log n)$ multiplicative ratio and an $O(\sqrt{n})$ additive error, where $n$ is the total number of nodes in the social graph. Moreover, we empirically verify the concentration condition in real-world networks and experimentally demonstrate the effectiveness of our proposed algorithm comparing to commonly adopted benchmark algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Online Vertex Cover and Matching: Beating the Greedy Algorithm

In this paper, we explicitly study the online vertex cover problem, which is a natural generalization of the well-studied ski-rental problem. In the online vertex cover problem, we are required to maintain a monotone vertex cover in a graph whose vertices arrive online. When a vertex arrives, all its incident edges to previously arrived vertices are revealed to the algorithm. For bipartite graphs with the left vertices offline (i.e. all of the left vertices arrive first before any right vertex), there are algorithms achieving the optimal competitive ratio of $\frac{1}{1-1/e}\approx 1.582$. Our first result is a new optimal water-filling algorithm for this case. One major ingredient of our result is a new charging-based analysis, which can be generalized to attack the online fractional vertex cover problem in general graphs. The main contribution of this paper is a 1.901-competitive algorithm for this problem. When the underlying graph is bipartite, our fractional solution can be rounded to an integral solution. In other words, we can obtain a vertex cover with expected size at most 1.901 of the optimal vertex cover in bipartite graphs. The next major result is a primal-dual analysis of our algorithm for the online fractional vertex cover problem in general graphs, which implies the dual result of a 0.526-competitive algorithm for online fractional matching in general graphs. Notice that both problems admit a well-known 2-competitive greedy algorithm. Our result in this paper is the first successful attempt to beat the greedy algorithm for these two problems. On the hardness side, we show that no randomized online algorithm can achieve a competitive ratio better than 1.753 and 0.625 for the online fractional vertex cover problem and the online fractional matching problem respectively, even for bipartite graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Sybil-proof Mechanisms in Query Incentive Networks

In this paper, we study incentive mechanisms for retrieving information from networked agents. Following the model in [Kleinberg and Raghavan 2005], the agents are represented as nodes in an infinite tree, which is generated by a random branching process. A query is issued by the root, and each node possesses an answer with an independent probability $p=1/n$. Further, each node in the tree acts strategically to maximize its own payoff. In order to encourage the agents to participate in the information acquisition process, an incentive mechanism is needed to reward agents who provide the information as well as agents who help to facilitate such acquisition. We focus on designing efficient sybil-proof incentive mechanisms, i.e., which are robust to fake identity attacks. %We consider incentive mechanisms which are sybil-proof, i.e., robust to fake identity attacks. We propose a family of mechanisms, called the direct referral (DR) mechanisms, which allocate most reward to the information holder as well as its direct parent (or direct referral). We show that, when designed properly, the direct referral mechanism is sybil-proof and efficient. In particular, we show that we may achieve an expected cost of $O(h^2)$ for propagating the query down $h$ levels for any branching factor $b>1$. This result exponentially improves on previous work when requiring to find an answer with high probability. When the underlying network is a deterministic chain, our mechanism is optimal under some mild assumptions. In addition, due to its simple reward structure, the DR mechanism might have good chance to be adopted in practice.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems

We study the matroid secretary problems with submodular valuation functions. In these problems, the elements arrive in random order. When one element arrives, we have to make an immediate and irrevocable decision on whether to accept it or not. The set of accepted elements must form an {\em independent set} in a predefined matroid. Our objective is to maximize the value of the accepted elements. In this paper, we focus on the case that the valuation function is a non-negative and monotonically non-decreasing submodular function. We introduce a general algorithm for such {\em submodular matroid secretary problems}. In particular, we obtain constant competitive algorithms for the cases of laminar matroids and transversal matroids. Our algorithms can be further applied to any independent set system defined by the intersection of a {\em constant} number of laminar matroids, while still achieving constant competitive ratios. Notice that laminar matroids generalize uniform matroids and partition matroids. On the other hand, when the underlying valuation function is linear, our algorithm achieves a competitive ratio of 9.6 for laminar matroids, which significantly improves the previous result.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships

Influence diffusion and influence maximization in large-scale online social networks (OSNs) have been extensively studied, because of their impacts on enabling effective online viral marketing. Existing studies focus on social networks with only friendship relations, whereas the foe or enemy relations that commonly exist in many OSNs, e.g., Epinions and Slashdot, are completely ignored. In this paper, we make the first attempt to investigate the influence diffusion and influence maximization in OSNs with both friend and foe relations, which are modeled using positive and negative edges on signed networks. In particular, we extend the classic voter model to signed networks and analyze the dynamics of influence diffusion of two opposite opinions. We first provide systematic characterization of both short-term and long-term dynamics of influence diffusion in this model, and illustrate that the steady state behaviors of the dynamics depend on three types of graph structures, which we refer to as balanced graphs, anti-balanced graphs, and strictly unbalanced graphs. We then apply our results to solve the influence maximization problem and develop efficient algorithms to select initial seeds of one opinion that maximize either its short-term influence coverage or long-term steady state influence coverage. Extensive simulation results on both synthetic and real-world networks, such as Epinions and Slashdot, confirm our theoretical analysis on influence diffusion dynamics, and demonstrate the efficacy of our influence maximization algorithm over other heuristic algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Information Dissemination via Random Walks in d-Dimensional Space

We study a natural information dissemination problem for multiple mobile agents in a bounded Euclidean space. Agents are placed uniformly at random in the $d$-dimensional space $\{-n, ..., n\}^d$ at time zero, and one of the agents holds a piece of information to be disseminated. All the agents then perform independent random walks over the space, and the information is transmitted from one agent to another if the two agents are sufficiently close. We wish to bound the total time before all agents receive the information (with high probability). Our work extends Pettarin et al.'s work (Infectious random walks, arXiv:1007.1604v2, 2011), which solved the problem for $d \leq 2$. We present tight bounds up to polylogarithmic factors for the case $d = 3$. (While our results extend to higher dimensions, for space and readability considerations we provide only the case $d=3$ here.) Our results show the behavior when $d \geq 3$ is qualitatively different from the case $d \leq 2$. In particular, as the ratio between the volume of the space and the number of agents varies, we show an interesting phase transition for three dimensions that does not occur in one or two dimensions.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Optimal Pricing in Social Networks with Incomplete Information

In revenue maximization of selling a digital product in a social network, the utility of an agent is often considered to have two parts: a private valuation, and linearly additive influences from other agents. We study the incomplete information case where agents know a common distribution about others' private valuations, and make decisions simultaneously. The "rational behavior" of agents in this case is captured by the well-known Bayesian Nash equilibrium. Two challenging questions arise: how to compute an equilibrium and how to optimize a pricing strategy accordingly to maximize the revenue assuming agents follow the equilibrium? In this paper, we mainly focus on the natural model where the private valuation of each agent is sampled from a uniform distribution, which turns out to be already challenging. Our main result is a polynomial-time algorithm that can exactly compute the equilibrium and the optimal price, when pairwise influences are non-negative. If negative influences are allowed, computing any equilibrium even approximately is PPAD-hard. Our algorithm can also be used to design an FPTAS for optimizing discriminative price profile.

0 citations0 reviewsNo code linkedOpen access