Search

The class of random features is one of the most popular techniques to speed up kernel methods in large-scale problems. Related works have been recognized by the NeurIPS Test-of-Time award in 2017 and the ICML Best Paper Finalist in 2019. The body of work on random features has grown rapidly, and hence it is desirable to have a comprehensive overview on this topic explaining the connections among various algorithms and theoretical results. In this survey, we systematically review the work on random features from the past ten years. First, the motivations, characteristics and contributions of representative random features based algorithms are summarized according to their sampling schemes, learning procedures, variance reduction properties and how they exploit training data. Second, we review theoretical results that center around the following key question: how many random features are needed to ensure a high approximation quality or no loss in the empirical/expected risks of the learned estimator. Third, we provide a comprehensive evaluation of popular random features based algorithms on several large-scale benchmark datasets and discuss their approximation quality and prediction performance for classification. Last, we discuss the relationship between random features and modern over-parameterized deep neural networks (DNNs), including the use of high dimensional random features in the analysis of DNNs as well as the gaps between current theoretical and empirical results. This survey may serve as a gentle introduction to this topic, and as a users’ guide for practitioners interested in applying the representative algorithms and understanding theoretical results under various technical assumptions. We hope that this survey will facilitate discussion on the open problems in this topic, and more importantly, shed light on future research directions. Due to the page limit, we suggest the readers refer to the full version of this survey https://arxiv.org/abs/2004.11154. [ABSTRACT FROM AUTHOR]

By employing time-varying proximal functions, adaptive subgradient methods (ADAGRAD) have improved the regret bound and been widely used in online learning and optimization. However, ADAGRAD with full matrix proximal functions (ADA-FULL) cannot handle large-scale problems due to the impractical $O(d^3)$ O (d 3) time and $O(d^2)$ O (d 2) space complexities, though it has better performance when gradients are correlated. In this paper, we propose two efficient variants of ADA-FULL via a matrix sketching technique called frequent directions (FD). The first variant named as ADA-FD directly utilizes FD to maintain and manipulate low-rank matrices, which reduces the space and time complexities to $O(\tau d)$ O (τ d) and $O(\tau ^2d)$ O (τ 2 d) respectively, where $d$ d is the dimensionality and $\tau \ll d$ τ ≪ d is the sketching size. The second variant named as ADA-FFD further adopts a doubling trick to accelerate FD used in ADA-FD, which reduces the average time complexity to $O(\tau d)$ O (τ d) while only doubles the space complexity of ADA-FD. Theoretical analysis reveals that the regret of ADA-FD and ADA-FFD is close to that of ADA-FULL as long as the outer product matrix of gradients is approximately low-rank. Experimental results demonstrate the efficiency and effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

This article proposes an offline control algorithm, called recurrent model predictive control, to solve large-scale nonlinear finite-horizon optimal control problems. It can be regarded as an explicit solver of traditional model predictive control (MPC) algorithms, which can adaptively select appropriate model prediction horizon according to current computing resources, so as to improve the policy performance. Our algorithm employs a recurrent function to approximate the optimal policy, which maps the system states and reference values directly to the control inputs. The output of the learned policy network after $N$ recurrent cycles corresponds to the nearly optimal solution of $N$ -step MPC. A policy optimization objective is designed by decomposing the MPC cost function according to the Bellman’s principle of optimality. The optimal recurrent policy can be obtained by directly minimizing the designed objective function, which is applicable for general nonlinear and noninput-affine systems. Both simulation-based and real-robot path-tracking tasks are utilized to demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Subgraph queries are routinely used to search for entities in richly attributed graphs e.g., social networks and knowledge graphs. With little knowledge of underlying data, users often need to rewrite queries multiple times to reach desirable answers. Why-questions are studied to clarify missing or unexpected query results. This paper makes a first step to answer Why-questions for entity search in attributed graphs. We consider three common types of Why-questions: Why-not, Why, and Why-rank, which suggest query manipulations that are responsible for user-specified missing, unexpected, and undesirably ranked entities, respectively. (1) We approach a general query rewriting paradigm that suggests to identify desired entities that are specified by Why-questions. We introduce measures that characterize good query rewrites by incorporating both query editing cost and answer closeness. (2) While computing optimal query rewrites is intractable, we develop feasible algorithms, from approximation to fast heuristics, and provide query rewrites with (near) optimality guarantees whenever possible, for Why, Why-not and Why-rank questions. We further show that our results remain intact for Why questions that (1) request a single query rewrite to clarify multiple types of entities, and (2) variants such as Why-empty and Why-so-many, by providing the matching algorithms. Using real-world graphs, we experimentally verify that our algorithms are effective and feasible for large graphs. Our case study also verifies their application in e.g., knowledge exploration. [ABSTRACT FROM AUTHOR]

Data deduplication saves storage space by identifying and removing repeats in the data stream. Compared with traditional compression methods, data deduplication schemes are more computationally efficient and are thus widely used in large scale storage systems. In this paper, we provide an information-theoretic analysis of the performance of deduplication algorithms on data streams in which repeats are not exact. We introduce a source model in which probabilistic substitutions are considered. More precisely, each symbol in a repeated string is substituted with a given edit probability. Deduplication algorithms in both the fixed-length scheme and the variable-length scheme are studied. The fixed-length deduplication algorithm is shown to be unsuitable for the proposed source model as it does not take into account the edit probability. Two modifications are proposed and shown to have performances within a constant factor of optimal for a specific class of source models with the knowledge of model parameters. We also study the conventional variable-length deduplication algorithm and show that as source entropy becomes smaller, the size of the compressed string vanishes relative to the length of the uncompressed string, leading to high compression ratios. [ABSTRACT FROM AUTHOR]

In applications of remote sensing, estimation, and control, timely communication is critical but not always ensured by high-rate communication. This work proposes decentralized age-efficient transmission policies for random access channels with $M$ transmitters. We propose the notion of age-gain of a packet to quantify how much the packet will reduce the instantaneous age of information at the receiver side upon successful delivery. We then utilize this notion to propose a transmission policy in which transmitters act in a decentralized manner based on the age-gain of their available packets. In particular, each transmitter sends its latest packet only if its corresponding age-gain is beyond a certain threshold which could be computed adaptively using the collision feedback or found as a fixed value analytically in advance. Both methods improve age of information significantly compared to the state of the art. In the limit of large $M$ , we prove that when the arrival rate is small (below $\frac {1}{eM}$), slotted ALOHA-type algorithms are order optimal. As the arrival rate increases beyond $\frac {1}{eM}$ , while age increases under slotted ALOHA, it decreases significantly under the proposed age-based policies. For arrival rates $\theta $ , $\theta =\frac {1}{o(M)}$ , the proposed algorithms provide a multiplicative gain of at least two compared to the minimum age under slotted ALOHA (minimum over all arrival rates). We conclude that it is beneficial to increase the sampling rate (and hence the arrival rate) and transmit packets selectively based on their age-gain. This is surprising and contrary to common practice where the arrival rate is optimized to attain the minimum AoI. We further extend our results to other random access technologies such as Carrier-sense multiple access (CSMA). [ABSTRACT FROM AUTHOR]

Faced with massive data, subsampling is a commonly used technique to improve computational efficiency, and using nonuniform subsampling probabilities is an effective approach to improve estimation efficiency. For computational efficiency, subsampling is often implemented with replacement or through Poisson subsampling. However, no rigorous investigation has been performed to study the difference between the two subsampling procedures such as their estimation efficiency and computational convenience. This paper performs a comparative study on these two different sampling procedures. In the context of maximizing a general target function, we first derive asymptotic distributions for estimators obtained from the two sampling procedures. The results show that the Poisson subsampling may have a higher estimation efficiency. Based on the asymptotic distributions for both subsampling with replacement and Poisson subsampling, we derive optimal subsampling probabilities that minimize the variance functions of the subsampling estimators. These subsampling probabilities further reveal the similarities and differences between subsampling with replacement and Poisson subsampling. The theoretical characterizations and comparisons on the two subsampling procedures provide guidance to select a more appropriate subsampling approach in practice. Furthermore, practically implementable algorithms are proposed based on the optimal structural results, which are evaluated through both theoretical and empirical analyses. [ABSTRACT FROM AUTHOR]

This article investigates the finite-time distributed approximate optimization problem of higher order multiagent systems, where the local cost functions are considered to be quadratic functions. This problem is solved via penalty-function-based method. First, by the penalty-function method, a global approximate cost function is constructed. Second, nonlinear distributed optimization algorithms are proposed for higher order multiagent systems by the tool of adding a power integrator technique. In the optimization algorithms design, the gradients of the approximate cost function are utilized. Under the proposed optimization algorithms, the agents approach the approximate optimal solution in finite time. Although there exist errors (they may be called approximation errors) between the approximate minimizers and the global accurate minimizer, the approximation errors can be regulated by penalty parameter and the relationship between the bound of the approximation errors and the penalty parameter is given explicitly. Furthermore, the proposed distributed approximate optimization algorithms are applied to the optimal rendezvous problem of wheeled multimobile robots, making the mobile robots achieve approximate optimization rendezvous in finite time. The effectiveness of the proposed distributed optimization algorithms and their applications to optimal rendezvous problem are validated by simulations. [ABSTRACT FROM AUTHOR]

In this article, we discuss a sequential algorithm for the computation of a minimum-time speed profile over a given path, under velocity, acceleration, and jerk constraints. Such a problem arises in industrial contexts, such as automated warehouses, where LGVs need to perform assigned tasks as fast as possible in order to increase productivity. It can be reformulated as an optimization problem with a convex objective function, linear velocity and acceleration constraints, and nonconvex jerk constraints, which, thus, represent the main source of the difficulty. While existing nonlinear programming (NLP) solvers can be employed for the solution of this problem, it turns out that the performance and robustness of such solvers can be enhanced by the sequential line-search algorithm proposed in this article. At each iteration, a feasible direction, with respect to the current feasible solution, is computed, and a step along such direction is taken in order to compute the next iterate. The computation of the feasible direction is based on the solution of a linearized version of the problem, and the solution of the linearized problem, through an approach that strongly exploits its special structure, represents the main contribution of this work. The efficiency of the proposed approach with respect to existing NLP solvers is proven through different computational experiments. Note to Practitioners—This article was motivated by the needs of LGV manufacturers. In particular, it presents an algorithm for computing the minimum-time speed law for an LGV along a preassigned path, respecting assigned velocity, acceleration, and jerk constraints. The solution algorithm should be: 1) fast, since speed planning is made continuously throughout the workday, not only when an LGV receives a new task but also during the execution of the task itself, since conditions may change, e.g., if the LGV has to be halted for security reasons and 2) reliable, i.e., it should return solutions of high quality, because a better speed profile allows to save time and even small percentage improvements, say a 5% improvement, has a considerable impact on the productivity of the warehouse, and, thus, determines a significant economic gain. The algorithm that we propose meets these two requirements, and we believe that it can be a useful tool for LGV manufacturers and users. It is obvious that the proposed method also applies to the speed planning problem for vehicles other than LGVs, e.g., road vehicles. [ABSTRACT FROM AUTHOR]

In this article, we design algorithms to protect swarm-robotics applications against sensor denial-of-service attacks on robots. We focus on applications requiring the robots to jointly select actions, e.g., which trajectory to follow, among a set of available actions. Such applications are central in large-scale robotic applications, such as multirobot motion planning for target tracking. But the current attack-robust algorithms are centralized. In this article, we propose a general-purpose distributed algorithm toward robust optimization at scale, with local communications only. We name it distributed robust maximization (DRM). DRM proposes a divide-and-conquer approach that distributively partitions the problem among cliques of robots. Then, the cliques optimize in parallel, independently of each other. We prove DRM achieves a close-to-optimal performance. We demonstrate DRM’s performance in Gazebo and MATLAB simulations, in scenarios of active target tracking with swarms of robots. In the simulations, DRM achieves computational speed-ups, being 1 to 2 orders faster than the centralized algorithms. Yet, it nearly matches the tracking performance of the centralized counterparts. Since, DRM overestimates the number of attacks in each clique, in this article, we also introduce an improved distributed robust maximization (IDRM) algorithm. IDRM infers the number of attacks in each clique less conservatively than DRM by leveraging three-hop neighboring communications. We verify IDRM improves DRM’s performance in simulations. [ABSTRACT FROM AUTHOR]

Given $m~d$ -dimensional responsors and $n~d$ -dimensional predictors, sparse regression finds at most $k$ predictors for each responsor for linear approximation, $1\leq k \leq d-1$. The key problem in sparse regression is subset selection, which usually suffers from high computational cost. In recent years, many improved approximate methods of subset selection have been published. However, less attention has been paid to the nonapproximate method of subset selection, which is very necessary for many questions in data analysis. Here, we consider sparse regression from the view of correlation and propose the formula of conditional uncorrelation. Then, an efficient nonapproximate method of subset selection is proposed in which we do not need to calculate any coefficients in the regression equation for candidate predictors. By the proposed method, the computational complexity is reduced from $O([{1}/{6}]{k^{3}}\!+(m+1)k^{2}\!+\!mkd)$ to $O([{1}/{6}]{k^{3}}\!+[{1}/{2}](m+1)k^{2})$ for each candidate subset in sparse regression. Because the dimension $d$ is generally the number of observations or experiments and large enough, the proposed method can greatly improve the efficiency of nonapproximate subset selection. We also apply the proposed method in real scenarios of dental age assessment and sparse coding to validate the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

This article is concerned with a distributed filtering problem for Markov jump systems subject to the measurement loss with unknown probabilities. A centralized robust Kalman filter is designed by using variational Bayesian methods and a modified interacting multiple model method based on information theory (IT-IMM). Then, a distributed robust Kalman filter based on the centralized filter and a hybrid consensus method called hybrid consensus on measurement and information (HCMCI) is designed. Moreover, boundedness of the estimation errors and the estimation error covariances are studied for the distributed robust Kalman filter. [ABSTRACT FROM AUTHOR]

We study a class of generic charging path optimization problems arising from emerging networking applications, where mobile chargers are dispatched to deliver energy to mobile agents (e.g., robots, drones, vehicles), which have specified tasks and mobility patterns. We instantiate our work by focusing on finding the charging path maximizing the number of nodes charged within a fixed time horizon. We show that this problem is APX-hard. By recursively decomposing the problem into sub-problems of searching sub-paths, we design quasi-polynomial-time algorithms achieving logarithmic approximation to the optimum charging path. Our approximation algorithms can be further adapted and extended to solve a variety of charging path optimization and scheduling problems with realistic constraints, such as limited time and energy budget. [ABSTRACT FROM AUTHOR]

Mobile edge computing (MEC) is an emerging architecture for accommodating latency sensitive virtualized services (VSs). Many of these VSs are expected to be safety critical, and will have some form of reliability requirements. In order to support provisioning reliability to such VSs in MEC in an efficient and confidentiality preserving manner, in this paper we consider the joint resource dimensioning and placement problem for VSs with diverse reliability requirements, with the objective of minimizing the energy consumption. We formulate the problem as an integer programming problem, and prove that it is NP-hard. We propose a two-step approximation algorithm with bounded approximation ratio based on Lagrangian relaxation. We benchmark our algorithm against two greedy algorithms in realistic scenarios. The results show that the proposed solution is computationally efficient, scalable and can provide up to 30 percent reduction in energy consumption compared to greedy algorithms. [ABSTRACT FROM AUTHOR]

Seismic data acquired in a desert environment often have a low signal-to-noise ratio, posing a significant challenge to seismic processing, imaging, and inversion. Nonlinear beamforming is one effective method that uses local second-order mathematical operators to describe seismic events and then enhance them. However, estimating the operator coefficients from input data is a nonlinear and compute-intensive optimization problem. We propose a new method for this estimation based on a recently developed efficiency-improved genetic algorithm. We demonstrate that it delivers an excellent balance between improved data quality and computational efficiency. We also introduce a “spatial consistency” feature to further speed up the algorithm by using available nonlinear-beamforming operators as initial trial solutions for the neighboring data ensembles. These findings are supported by applying the new approach to land seismic datasets from the desert environment. [ABSTRACT FROM AUTHOR]

This article is the second part of a two-part survey series on large-scale global optimization. The first part covered two major algorithmic approaches to large-scale optimization, namely, decomposition methods and hybridization methods, such as memetic algorithms and local search. In this part, we focus on sampling and variation operators, approximation and surrogate modeling, initialization methods, and parallelization. We also cover a range of problem areas in relation to large-scale global optimization, such as multiobjective optimization, constraint handling, overlapping components, the component imbalance issue and benchmarks, and applications. The article also includes a discussion on pitfalls and challenges of the current research and identifies several potential areas of future research. [ABSTRACT FROM AUTHOR]

In this letter, an efficient millimeter-wave (MMW) frequency-domain imaging algorithm is presented for 3-D object reconstruction of the near-field multiple-input–multiple-output synthetic aperture radar (MIMO-SAR) with nonuniform transmitting array. For each single-input–multiple-output (SIMO) case of the MIMO-SAR setup, the precise spectral echo expression is derived by spherical-wave decomposition and fast Fourier transform (FFT) operations. To obtain the linear phase in range direction, the multiorder approximation theory is employed to expand the coupling phases, and thus the target subimage can be reconstructed by utilizing phase compensation, central wavenumber approximation, and inverse FFT. Finally, the fully focused 3-D image for MIMO setup will be realized through accumulating all the SIMO subimages. Compared with the existing representative algorithms, our method avoids complicated interpolation and achieves high-quality fast imaging with only matrix multiplication and a small amount of iteration operations. The experimental results validate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In recent years, we have witnessed a growing use of unmanned aerial vehicles (UAVs) in a variety of civil, commercial and military applications. Among these applications, many require the UAVs to scan or survey one or more regions, such as land monitoring, disaster assessment, search and rescue. To realize such applications, path planning is a key step. Although the coverage path planning (CPP) problem for a single region has been extensively studied in the literature, CPP for multiple regions has gained much less attention. This multi-regional CPP problem can be considered as a variant of the (multiple) traveling salesman problem (TSP) enhanced with CPP. Previously, we have studied the case of a single UAV. In this paper, we extend our previous studies to further consider multiple UAVs with energy constraints. To solve this new path planning problem, we develop two approaches: 1) a branch-and-bound (BnB) based approach that can find (near) optimal tours and 2) a genetic algorithm (GA) based approach that can solve large-scale problems efficiently under different objectives. Comprehensive theoretical analyses and computational experiments demonstrate the promising performance of the proposed approaches in terms of optimality and efficiency. [ABSTRACT FROM AUTHOR]

This article focuses on developing a static output feedback (SOF) control scheme for Takagi–Sugeno fuzzy systems. The proposed SOF controller does not share the same premise membership functions with the model, which permits enhancing the flexibility in controller design and implementation. By contrast with the state feedback case, the SOF control generally results in nonconvex design conditions. To circumvent this problem, we develop a successive convex optimization algorithm, which is based on solving a sequence of more tractable convex optimization problems obtained by approximating the nonconvex constraints with some convex ones. As a heuristic algorithm, the validity of the developed successive convex optimization algorithm is highly affected by initial conditions, and, recognizing this, we put forward an iterative procedure for determining the feasible initial condition. Finally, two illustrative examples are presented to validate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Rough clustering has attracted increasing attention due to well dealing with the fuzziness and uncertainty of data. It is well known that it needs to manually set the threshold to determine the upper and lower approximations of rough clusters, which may bring a great effect on the clustering performance. When applied to image segmentation, rough clustering is always sensitive to the initialized cluster centers and image noise. Furthermore, only one clustering criterion is considered in rough clustering, which cannot satisfy diverse practical requirements. To handle these issues, a particle competitive mechanism based multiobjective rough clustering algorithm (PCM-MORCA) for image segmentation is proposed. First, a rough intraclass compactness function considering the nonlocal spatial information derived from an image is constructed to overcome the sensitivity to image noise. Next, the constructed rough intraclass compactness function and an interclass separation function are optimized simultaneously to make cluster centers meet diverse segmentation requirements. Then, an adaptive threshold determination mechanism by which the threshold adaptively varies with the clustered data is presented to well determine the upper and lower approximations of rough clusters. After that, to effectively search appropriate cluster centers, a novel pair competition-based particle weight updating strategy is designed for multiobjective particle swarm optimization by improving the elite particle selection and particle update. Finally, a rough clustering index with the nonlocal spatial information is constructed for selecting the optimal solution for PCM-MORCA. Segmentation experiments on Berkeley and magnetic resonance images reveal that PCM-MORCA behaves well on the segmentation accuracy and noise robustness. [ABSTRACT FROM AUTHOR]

With an increasing penetration of distributed energy resources (DERs), it has become a public interest regarding how to efficiently manage large-scale DERs into wholesale markets. The existing literature has focused on various coordination methods including iteration-based (e.g., Lagrangian relaxation) and projection-based (e.g., vertex enumeration) ones, which may not work for the cases with complicated constraints due to curse of dimensionality. In this article, we propose an efficient projection-based method that adapts to characterizing the feasible region of active distribution networks with temporal-coupled constraints. The problem of finding the temporal-coupled feasible region is formulated as a max–min optimization program, aiming to determine the largest set allowing zero-valued slack variables. Based on Duality Principle, the max–min model is transformed into a solvable mixed-integer linear programming that can be efficiently optimized by off-the-shelf solvers. In contrast to the existing methods searching for a vertex from interior points, we develop an outer progressive approximation algorithm that generates feasibility cuts for each iteration. Case studies based on a modified IEEE 33-bus feeder and Caracas 141-bus system demonstrate the effectiveness and efficiency of our proposed method in characterizing the feasible region with large-scale temporal-coupled constraints. [ABSTRACT FROM AUTHOR]

This paper explores the non-convex composition optimization consisting of inner and outer finite-sum functions with a large number of component functions. This problem arises in important applications such as nonlinear embedding and reinforcement learning. Although existing approaches such as stochastic gradient descent (SGD) and stochastic variance reduced gradient (SVRG) descent can be applied to solve this problem, their query complexities tend to be high, especially when the number of inner component functions is large. Therefore, to significantly improve the query complexity of current approaches, we have devised the stochastic composition via variance reduction (SCVR). What's more, we analyze the query complexity under different numbers of inner function and outer function. Based on different kinds of estimation of inner component function, we also present the SCVRII algorithm, though the order of query complexities are the same with SCVR. Additionally, we propose an extension to handle the mini-batch cases, which improve the query complexity under the optimal mini-batch size. The experimental results validate our proposed algorithms and theoretical analyses. [ABSTRACT FROM AUTHOR]

Binary optimization problems (BOPs) arise naturally in many fields, such as information retrieval, computer vision, and machine learning. Most existing binary optimization methods either use continuous relaxation which can cause large quantization errors, or incorporate a highly specific algorithm that can only be used for particular loss functions. To overcome these difficulties, we propose a novel generalized optimization method, named Alternating Binary Matrix Optimization (ABMO), for solving BOPs. ABMO can handle BOPs with/without orthogonality or linear constraints for a large class of loss functions. ABMO involves rewriting the binary, orthogonality and linear constraints for BOPs as an intersection of two closed sets, then iteratively dividing the original problems into several small optimization problems that can be solved as closed forms. To provide a strict theoretical convergence analysis, we add a sufficiently small perturbation and translate the original problem to an approximated problem whose feasible set is continuous. We not only provide rigorous mathematical proof for the convergence to a stationary and feasible point, but also derive the convergence rate of the proposed algorithm. The promising results obtained from four binary optimization tasks validate the superiority and the generality of ABMO compared with the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Social-media platforms have created new ways for citizens to stay informed and participate in public debates. However, to enable a healthy environment for information sharing, social deliberation, and opinion formation, citizens need to be exposed to sufficiently diverse viewpoints that challenge their assumptions, instead of being trapped inside filter bubbles. In this paper, we take a step in this direction and propose a novel approach to maximize the diversity of exposure in a social network. We formulate the problem in the context of information propagation, as a task of recommending a small number of news articles to selected users. In the proposed setting, we take into account content and user leanings, and the probability of further sharing an article. Our model allows to capture the balance between maximizing the spread of information and ensuring the exposure of users to diverse viewpoints. The resulting problem can be cast as maximizing a monotone and submodular function, subject to a matroid constraint on the allocation of articles to users. It is a challenging generalization of the influence-maximization problem. Yet, we are able to devise scalable approximation algorithms by introducing a novel extension to the notion of random reverse-reachable sets. We experimentally demonstrate the efficiency and scalability of our algorithm on several real-world datasets. [ABSTRACT FROM AUTHOR]

Driven by real-life applications in geo-social networks, we study the problem of computing radius-bounded $k$ k -cores (RB- $k$ k -cores) that aims to find communities satisfying both social and spatial constraints. In particular, the model $k$ k -core (i.e., the subgraph where each vertex has at least $k$ k neighbors) is used to ensure the social cohesiveness, and a radius-bounded circle is used to restrict the locations of users in an RB- $k$ k -core. We explore several algorithmic paradigms to compute RB- $k$ k -cores, including a triple-vertex-based paradigm, a binary-vertex-based paradigm, and a paradigm utilizing the concept of rotating circles. The rotating-circle-based paradigm is further enhanced by several pruning techniques to achieve better efficiency. In addition, to find representative RB- $k$ k -cores, we study the diversified radius-bounded $k$ k -core search problem, which finds $t$ t RB- $k$ k -cores to cover the most number of vertices. We first propose a baseline algorithm that identifies the distinctive RB- $k$ k -cores after finding all the RB- $k$ k -cores. Beyond this, we design algorithms that can efficiently maintain the top- $t$ t candidate RB- $k$ k -cores and also achieve a guaranteed approximation ratio. Experimental studies on both real and synthetic datasets demonstrate that our proposed techniques can efficiently compute (diversified) RB- $k$ k -cores. Moreover, our techniques can be used to compute the minimum-circle-bounded $k$ k -core and significantly outperform the existing techniques. [ABSTRACT FROM AUTHOR]

Cliques refer to subgraphs in an undirected graph such that vertices in each subgraph are pairwise adjacent. The maximum clique problem, to find the clique with most vertices in a given graph, has been extensively studied. Besides its theoretical value as an NP-hard problem, the maximum clique problem is known to have direct applications in various fields, such as community search in social networks and social media, team formation in expert networks, gene expression and motif discovery in bioinformatics and anomaly detection in complex networks, revealing the structure and function of networks. However, algorithms designed for the maximum clique problem are expensive to deal with real-world networks. In this paper, we first devise a randomized algorithm for the maximum clique problem. Different from previous algorithms that search from each vertex one after another, our approach RMC, for the randomized maximum clique problem, employs a binary search while maintaining a lower bound $\underline{\omega _c}$ ω c ̲ and an upper bound $\overline{\omega _c}$ ω c ¯ of $\omega (G)$ ω (G) . In each iteration, RMC attempts to find a $\omega _t$ ω t -clique where $\omega _t=\lfloor (\underline{\omega _c}+\overline{\omega _c})/2\rfloor$ ω t = ⌊ (ω c ̲ + ω c ¯) / 2 ⌋ . As finding $\omega _t$ ω t in each iteration is NP-complete, we extract a seed set $S$ S such that the problem of finding a $\omega _t$ ω t -clique in $G$ G is equivalent to finding a $\omega _t$ ω t -clique in $S$ S with probability guarantees ($\geq$ ≥ $ 1-n^{-c}$ 1 - n - c ). We propose a novel iterative algorithm to determine the maximum clique by searching a $k$ k -clique in $S$ S starting from $k=\underline{\omega _c}+1$ k = ω c ̲ + 1 until $S$ S becomes $\lbrace \rbrace$ { } , when more iterations benefit marginally. Due to the potential inconsistency of maximum clique algorithms, we study the problem of maximum clique enumeration and propose an efficient algorithm RMCE to enumerate all maximum cliques in a given graph. As confirmed by the experiments, both RMC and RMCE are much more efficient and robust than previous solutions, RMC can always find the exact maximum clique, and RMCE can always enumerate all maximum cliques in a given graph. [ABSTRACT FROM AUTHOR]

Reorganizing bus frequencies to cater for the actual travel demands can significantly save the cost of the public transport system. Many, if not all, previous studies formulate this as a bus frequency optimization problem that tries to minimize passengers’ average waiting time. On the other hand, many investigations have confirmed that the user satisfaction drops faster as the waiting time increases. Consequently, this paper studies the bus frequency optimization problem considering the user satisfaction. Specifically, for the first time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold can be maximized. We propose two variants of the problem, FAST and FASTCO, to cater for different application needs and prove that both are NP-hard. To solve FAST effectively and efficiently, we first present an index-based $(1-1/e)$ (1 - 1 / e) -approximation algorithm. By exploiting the locality property of routes in a bus network, we further propose a partition-based greedy method that achieves a $(1-\rho)(1-1/e)$ (1 - ρ) (1 - 1 / e) approximation ratio. Then we propose a progressive partition-based greedy method to further boost the efficiency while achieving a $(1-\rho)(1-1/e-\varepsilon)$ (1 - ρ) (1 - 1 / e - ɛ) approximation ratio. For the FASTCO problem, two greedy-based heuristic methods are proposed. Experiments on a real city-wide bus dataset in Singapore have been conducted to verify the efficiency, effectiveness, and scalability of our methods in addressing FAST and FASTCO respectively. [ABSTRACT FROM AUTHOR]

Revenue maximization (RM) is one of the most important problems in social networks, which attempts to find a small subset of users that make the expected revenue maximized. It has been studied in depth before. However, most of the existing literature was based on nonadaptive seeding strategies and simple information diffusion models. It considered the number of influenced users as a measurement unit to quantify the revenue. Until the emergence of the collaborate game model, it considered the activity as a basic object to compute the revenue. An activity initiated by a user can only influence those users whose distances are within ${k}$ -hop from the initiator. Based on that, we adopt an adaptive seed strategy and formulate an RM under the size budget (RMSB) problem. If taking into account the product’s promotion, we extend it to an RM under the community budget problem, where the influence can be distributed over the whole network uniformly. We can prove that our objective function is adaptive monotone and not adaptive submodular, but it is adaptive submodular in some special cases. We study these two problems under both the special submodular cases and general nonsubmodular cases, and propose RMSBSolver and RMCBSolver to solve them with strong theoretical guarantees, respectively. In particular, we give a data-dependent approximation ratio by adaptive primal curvature for the RMSB in general nonsubmodular cases. Finally, we evaluate our proposed algorithms by conducting experiments on real datasets, and show the effectiveness and accuracy of our solutions. [ABSTRACT FROM AUTHOR]

The ever increasing technological demand for the DFT computation poses several challenges both to theory and hardware realization. The design of usual fast Fourier transform (FFT) algorithms seems to have reached a stage of diminishing returns in terms of performance. Alternatively, approximate transform methods have been demonstrated to provide substantial gains in terms of energy-efficiency and performance by tolerating small inaccuracies in the results. In this letter, we present a transform scaling method variant of the Cooley-Tukey algorithm to obtain DFT approximations of large blocksize. The proposed method scales up a given $N$ -point transformation to an $N^{2}$ -point transformation. Such scaling can be successively applied leading to $N^{2^{n}}$ -point transformations. We have fully presented the $32^{4}$ -point DFT approximation which stems from a multiplierless 32-point DFT approximation. The proposed approximation is equipped with a fast algorithm; we also supply the arithmetic complexity assessment and an error analysis. [ABSTRACT FROM AUTHOR]

Considering the $ \alpha$ -stable input signals and noises, several robust fractional-order adaptive filtering algorithms have been proposed in recent years. However, the mean-square performance analysis of the FoAF algorithm has not been well studied in the literature. Toward that end, this letter provide a theoretical mean-square performance analysis of the FoAF algorithm, involving transient and steady-state behavior. Furthermore, an improved fractional-order adaptive filtering algorithm is derived by utilizing the M-estimate technique. Simulation experiments verify the results of the theoretical analysis and demonstrate the advantages of the proposed algorithm in heavy-tailed non-Gaussian environments. [ABSTRACT FROM AUTHOR]

Complex approximate message passing (CAMP) algorithm is a promising compressed sensing (CS) method for inverse synthetic aperture radar (ISAR) imaging with the merits of fast convergence and good reconstruction. To improve the imaging performance and accelerate the convergence, a new strategy weighted CAMP based ISAR imaging method has been proposed. Rather than solving a sequence of weighted ${l}_{{1}}$ minimization problems, the weighted CAMP problem is solved directly by using a new weighted threshold, which not only ensures the convergence of the algorithm but also improves the convergence speed. To accelerate the convergence furtherly, a new point is chosen smartly in the scalar threshold function, which borrows the idea of fast iterative shrinkage-thresholding algorithm (FISTA). As weighting adaptively to the signal and the noise is more appropriate to maintain the target information and suppress the noise, random forests (RF) algorithm is employed to classify the signal and the noise, and strategy weighting is used based on the classification result. The proposed algorithm was applied into complex sinusoids, quasi-real, and real ISAR data. It has got the best imaging result among the algorithms of CAMP class and need less imaging time than CAMP and weighted CAMP (WCAMP). Therefore, the proposed algorithm is an efficient ISAR imaging method with good performance. [ABSTRACT FROM AUTHOR]

As a novel sensing paradigm, crowd sensing systems have gained great attention and been widely adopted in the environmental monitoring and calculation areas. In crowd sensing systems, mobile users provide their multiple resources to the requesters to execute tasks. Existing studies focus on the divisible task or one-to-one mapping for single resource allocation. However, this assumption does not hold for crowd sensing systems. Owing to the task attribute, some tasks cannot be divided into multiple parts to run on different devices. In addition, a high performance mobile device can execute multiple tasks simultaneously. We address the problem of multi-resource allocation in crowd sensing systems for the auction-based model considering many-to-one mapping for indivisible tasks, where many-to-one mapping allows one mobile device to provide multiple resources to execute one or more tasks. In this article, we study, for the first time to the best of our knowledge, a truthful mechanism that stimulates mobile users and requesters to declare their true values. We design a truthful double auction mechanism together with a payment scheme tailored to fit it that would help researchers understand how a truthful double auction mechanism can be designed. In addition, we prove that our proposed mechanism maintains budget-balance, individual rationality, and computational tractability. Furthermore, we analyze the approximation ratio of our proposed approximation algorithm. Experimental results demonstrate that our proposed mechanism has high computation efficiency and good performance. [ABSTRACT FROM AUTHOR]

The design of a fuzzy neural network (FNN) has long been a challenging problem since most methods rely on approximation error to train an FNN, which may easily result in overfitting phenomenon to degrade the generalization performance. To improve the generalization performance, an FNN with a multiobjective optimization algorithm (MOO-FNN) is proposed in this article. First, the multilevel learning objectives are designed around the generalization performance to guide the training process of an FNN. Then, the method utilizes the approximation error, the structure complexity, and the output smoothness indicators instead of a single indicator to improve the evaluation accuracy of generalization performance. Second, an MOO algorithm with continuous–discrete variables is developed to optimize the FNN. Then, MOO is able to use a novel particle update method to adjust both the structure and parameters rather than adjusting them separately, thereby achieving suitable generalization performance of the FNN. Third, the convergence of MOO-FNN is analyzed in detail to guarantee its successful applications. Finally, the experimental studies of MOO-FNN have been performed on model identification of nonlinear systems to verify the effectiveness. The results illustrate that MOO-FNN has a significant improvement over some state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Considering multi-user downlink ultra-high reliability and low latency communications (URLLC), this paper employs the artificial noise (AN) technique to establish a secure and covert broadcast communication paradigm for the first time. Specifically, a multi-antenna transmitter (Alice) broadcasts the confidential information to multiple legitimate users in the presence of a multi-antenna malicious warden (Willie) and a multi-antenna eavesdropper (Eve). It is well known that AN is an effective technique for securing the physical layer security (PLS) of signal transmissions. Nevertheless, AN emission also exposes the signal transmission and decreases the signal covertness. Taking into account the impact of short-packet URLLC transmissions, we investigate the joint optimization of the precoder and AN to maximize the secrecy rate under the covertness constraint. Although the considered problem is nonconvex, we propose a branch-reduce-and-bound (BRB)-based algorithm to solve it optimally. However, the nested-loop structure of the BRB-based algorithm incurs a high computational complexity. To strike a balance between the performance and computational complexity, we also propose a low-complexity penalty successive convex approximation (SCA)-based algorithm, whose performance approaches that of the optimal BRB-based algorithm, particularly in the low to medium transmit power regime. Simulation results demonstrate the excellent performance of our proposed optimization algorithms compared with various benchmark algorithms and unveil the importance of exploiting AN for secrecy provisioning. [ABSTRACT FROM AUTHOR]

This paper studies joint beamforming problems for an intelligent reflecting surface (IRS)-aided multi-cell multiple-input single-output (MISO) system, and the goal is to maximize the sum rate by jointly optimizing the transmit beamforming vectors at BSs and the reflective beamforming vector at the IRS, subject to the individual maximum transmit power constraints at BSs, and the reflection constraints at the IRS. Due to the formulated optimization problem is highly non-convex, we propose an alternating optimization (AO) algorithm based on successive convex approximation (SCA) such that the transmit and reflective beamforming vectors can be optimized alternately. We further consider the SINR balancing beamforming design scheme by maximizing the minimum SINR among all users to enhance the fairness among users, in which the transmit and reflective beamforming vectors are optimized in an alternating manner. The transmit beamforming vectors are optimized by the second-order-cone programming (SOCP) based on bisection method and the reflective beamforming vector is updated based on the technique of semidefinite relaxation (SDR). Simulation results show that the two proposed algorithms considerably outperform the benchmark zero-forcing (ZF) scheme. Moreover, the AO algorithm based on SCA has good communication performance than the other two schemes. And the AO algorithm based on bisection search guarantees the fairness for all users. [ABSTRACT FROM AUTHOR]

Extra large MIMO (XL-MIMO) systems are subject to spatial non-stationarity forming visibility regions (VRs), which leads to a sub-array-wise sparse structure of the channel matrix. When XL-MIMO systems operate in grant-free access mode, in which only a fraction of the potential users are active during a given time slot, it follows that the channel matrix possesses a doubly-sparse and user-specific structure such that the activity of each user and each sub-array can be jointly modeled by a nested Bernoulli-Gaussian distribution. This article considers the joint activity and channel estimation (JACE) problem in XL-MIMO systems subject to this so-defined spatial non-stationarity, tackling this challenging inference problem. Our main contributions are 1) to introduce the novel Bernoulli-Gaussian model to simultaneously capture the aforementioned two distinct structured sparsities, and 2) a new bilinear Bayesian inference algorithm capable of jointly estimating the associated channel coefficients, user activity patterns, sub-array activity patterns ($a.k.a$. spatial non-stationarity), boosted by expectation maximization (EM)-based auto-parameterization. In addition, to shed light on a realistic modeling of VRs, we also introduce a Matérn-cluster point process (MCPP)-based approach to imitate the clustered activity pattern due to spatial non-stationarity. The efficacy of the proposed bilinear JACE algorithm is confirmed by numerical simulations, which show that the proposed method not only significantly outperforms the state-of-the-art (SotA) but also can reach the performance of a genie-aided scheme over wide signal-to-noise-ratio (SNR) ranges, in both uniformly-random and MCPP-based sub-array activity scenarios. [ABSTRACT FROM AUTHOR]

With the integration of Mobile Edge Computing (MEC) and Network Function Virtualization (NFV), service providers are able to provide low-latency services to mobile users for profit. In this paper, we study the online service placement and request assignment problem in an MEC network, where service requests arrive one by one without the knowledge of future arrivals, and each arrived request demands a specific service with a tolerable service delay requirement with the aim to maximize the profit of the service provider, through admitting as many service requests as possible for a given monitoring period. This optimization objective is achieved by assigning service requests to appropriate cloudlets in the MEC network, pre-installing service instances into cloudlets to shorten service delays, and accommodating new services by revoking some idle service instances from cloudlets due to limited computing resources in MEC networks. In this paper, we first show that the problem is NP-hard. We then devise an efficient deep reinforcement learning algorithm for the online service placement and request assignment problem that consists of a deep reinforcement learning-based prediction mechanism for dynamic service placement, followed by a dynamic request assignment procedure to assign requests to cloudlets. We finally evaluate the performance of the proposed algorithms by conducting experiments through simulations. Simulation results demonstrate that the proposed algorithm is promising, improving performance by 46.8% compared with that of the comparison algorithms. [ABSTRACT FROM AUTHOR]

In this article, we consider the optimal coordination of automated vehicles at intersections under fixed crossing orders. We formulate the problem using direct optimal control and exploit the structure to construct a semidistributed primal-dual interior-point algorithm to solve it by parallelizing most of the computations. Differently from standard distributed optimization algorithms, where the optimization problem is split, in our approach we split the linear algebra steps, such that the algorithm takes the same steps as a fully centralized one, while still performing computations in a distributed fashion. We analyze the communication requirements of the algorithm, and propose an approximation scheme which can significantly reduce the data exchange. We demonstrate the effectiveness of the algorithm in hard but realistic scenarios, which show that the approximation leads to reductions in communicated data of almost 99% of the exact formulation, at the expense of less than 1% suboptimality. [ABSTRACT FROM AUTHOR]

A subset ${\mathcal{ S}}\subseteq V$ of vertices of an undirected graph $G=(V,E)$ is a hub cover when for each edge $(u,v) \in E$ , at least one of its endpoints belongs to ${\mathcal{ S}}$ , or there exists a vertex $r \in {\mathcal{ S}}$ that is a neighbor of both $u$ and $v$ . The problem of computing a minimum hub cover set in arbitrary graphs is NP-hard. This problem has applications for indexing large databases. This paper proposes $\Psi $ -MHC, the first approximation algorithm for the minimum hub cover set in arbitrary graphs to the best of our knowledge. The approximation ratio of this algorithm is $\ln \mu $ , where $\mu $ is upper bounded by $\min \left\{{\frac {1}{2}(\Delta +1)^{2}, \vert E\vert }\right\}$ and $\Delta $ is the degree of $G$ . The execution time of $\Psi $ -MHC is $O((\Delta + 1) \vert E \vert + \vert {\mathcal{ S}} \vert \vert V \vert)$ . Experimental results show that $\Psi $ -MHC far outperforms the theoretical approximation ratio for the input graph instances.

Graph burning is a process to determine the spreading of information in a graph. If a sequence of vertices burns all the vertices of a graph by following the graph burning process, then such a sequence is known as a burning sequence. The graph burning problem consists in finding a minimum length burning sequence for a given graph. The solution to this NP-hard combinatorial optimization problem helps quantify a graph’s vulnerability to contagion. This paper introduces a simple farthest-first traversal-based approximation algorithm for this problem over arbitrary graphs. We refer to this proposal as the Burning Farthest-First (BFF) algorithm. BFF runs in $O(n^{3})$ steps and has a tight approximation factor of $3-2/b(G)$ , where $b(G)$ is the size of an optimal solution. The main attribute of BFF is that it has a better approximation factor than the state-of-the-art approximation algorithms for arbitrary graphs, which report an approximation factor of 3. Despite being simple, BFF proved practical when tested over some benchmark datasets.

This work proposes a novel deep reinforcement learning (DRL)-based demand response algorithm for smart facilities energy management to minimize electricity costs while maintaining a satisfaction index. Specifically, to accommodate the characteristics of the decision-making problem, long short-term memory (LSTM) units are adopted to extract discriminative features from past electricity price sequences and fed into fully connected multi-layer perceptrons (MLPs) with the measured energy and time information, then a deep Q-network is developed to approximate the optimal policy. After that, an experimental setup is constructed to investigate the effectiveness of the proposed DRL-based demand response algorithm to bridge the gap between theoretical studies and practical implementations. Numerical results demonstrate that the proposed algorithm can handle energy management well for multiple smart facilities. Moreover, the proposed algorithm outperforms the model predictive control (MPC) strategy and uncontrolled solution and is close to the theoretical optimal control method. [ABSTRACT FROM AUTHOR]

Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices, where the quantum approximation optimization algorithm (QAOA) constitutes a promising candidate for demonstrating tangible quantum advantages based on NISQ devices. In this paper, we consider the maximum likelihood (ML) detection problem of binary symbols transmitted over a multiple-input and multiple-output (MIMO) channel, where finding the optimal solution is exponentially hard using classical computers. Here, we apply the QAOA for the ML detection by encoding the problem of interest into a level- $p$ QAOA circuit having $2p$ variational parameters, which can be optimized by classical optimizers. This level- $p$ QAOA circuit is constructed by applying the prepared Hamiltonian to our problem and the initial Hamiltonian alternately in $p$ consecutive rounds. More explicitly, we first encode the optimal solution of the ML detection problem into the ground state of a problem Hamiltonian. Using the quantum adiabatic evolution technique, we provide both analytical and numerical results for characterizing the evolution of the eigenvalues of the quantum system used for ML detection. Then, for level-1 QAOA circuits, we derive the analytical expressions of the expectation values of the QAOA and discuss the complexity of the QAOA based ML detector. Explicitly, we evaluate the computational complexity of the classical optimizer used and the storage requirement of simulating the QAOA. Finally, we evaluate the bit error rate (BER) of the QAOA based ML detector and compare it both to the classical ML detector and to the classical minimum mean squared error (MMSE) detector, demonstrating that the QAOA based ML detector is capable of approaching the performance of the classical ML detector. [ABSTRACT FROM AUTHOR]

Many time series data mining problems can be solved with repeated use of distance measure. Examples of such tasks include similarity search, clustering, classification, anomaly detection and segmentation. For over two decades it has been known that the Dynamic Time Warping (DTW) distance measure is the best measure to use for most tasks, in most domains. Because the classic DTW algorithm has quadratic time complexity, many ideas have been introduced to reduce its amortized time, or to quickly approximate it. One of the most cited approximate approaches is FastDTW. The FastDTW algorithm has well over a thousand citations and has been explicitly used in several hundred research efforts. In this work, we make a surprising claim. In any realistic data mining application, the approximate FastDTW is much slower than the exact DTW. This fact clearly has implications for the community that uses this algorithm: allowing it to address much larger datasets, get exact results, and do so in less time. [ABSTRACT FROM AUTHOR]

Since inaccuracies commonly exist in many applications, data uncertainty has become an important problem in database systems. To deal with data uncertainty, probabilistic databases can be used to store uncertain data, and querying facilities are provided to yield answers with confidence. However, the results from a query or mining process may not be reliable when the uncertainty propagates in the systems. In this paper, we leverage the power of crowdsourcing by designing a set of Human Intelligence Tasks, or HITs in short, to ask a crowd to improve the quality of uncertain data. In particular, we consider crowds consists of workers with diverse accuracy rates when answering the HITs. We design solutions to maximize the data quality with minimal number of HITs. There are two obstacles for this non-trivial optimization, which lead to very high computational cost for selecting the optimal set of HITs. First, members of a crowd may return incorrect answers with different probabilities. Second, the HITs decomposed from uncertain data are often correlated. We have addressed these challenges in this paper by designing an effective approximation algorithm and an efficient heuristic solution, especially for crowds with diverse individual accuracy rates. To further improve the efficiency, we derive tight lower and upper bounds for effective filtering and estimation. Extensive experiments on both a simulated crowd and a real crowdsourcing platform are conducted to evaluate our solutions. [ABSTRACT FROM AUTHOR]

In this study, macroscopic properties of the vector approximate message passing (VAMP) algorithm for inference of generalized linear models are investigated using a non-rigorous heuristic method of statistical mechanics when the true posterior cannot be used and the measurement matrix is a sample from rotation-invariant random matrix ensembles. The focus is on the correspondence between the non-rigorous replica analysis of statistical mechanics and the performance assessment of VAMP in the model-mismatched setting. The correspondence of this kind is well-known when the measurement matrix has independent and identically distributed entries. However, when the measurement matrix follows a general rotation-invariant matrix ensemble, the correspondence has been validated only under limited cases, such as the Bayes optimal inference or the convex empirical risk minimization. The result presented in this paper is to extend the scope of such correspondence. Herein, we heuristically derive the explicit formula of state-evolution equations, which macroscopically describe VAMP dynamics for the current model-mismatched case, and show that their fixed point is generally consistent with the replica symmetric solution obtained by the replica method of statistical mechanics. We also show that the fixed point of VAMP can exhibit a microscopic instability, which indicates that message variables continue to move by VAMP while their macroscopically summarized quantities converge to fixed values. The critical condition the for microscopic instability agrees with that for breaking the replica symmetry that is derived within the non-rigorous replica analysis. The results of the numerical experiments cross-check our findings. [ABSTRACT FROM AUTHOR]