Search

Toward better approximation for the minimum-weighted vertex cover (MWVC) problem in multiagent systems, we present a distributed algorithm from the perspective of learning in games. For self-organized coordination and optimization, we see each vertex as a potential game player who makes decisions using local information of its own and the immediate neighbors. The resulting Nash equilibrium is classified into two categories, i.e., the inferior Nash equilibrium (INE) and the dominant Nash equilibrium (DNE). We show that the optimal solution must be a DNE. To achieve better approximation ratios, local rules of perturbation and weighted memory are designed, with the former destroying the stability of an INE and the latter facilitating the refinement of a DNE. By showing the existence of an improvement path from any INE to a DNE, we prove that when the memory length is larger than 1, our algorithm converges in finite time to DNEs, which could not be improved by exchanging the action of a selected node with all its unselected neighbors. Moreover, additional freedom for solution efficiency refinement is provided by increasing the memory length. Finally, intensive comparison experiments demonstrate the superiority of the presented methodology to the state of the art, both in solution efficiency and computation speed. [ABSTRACT FROM AUTHOR]

This article investigates optimal control problem for a class of discrete-time (DT) nonlinear systems with unknown dynamics. With the help of a broad learning system (BLS), a novel online adaptive dynamic programming (ADP) controller is presented. First, to approximate the unknown system dynamics, an approximator based on BLS is presented. The connection weights are calculated by the data of the system by using the ridge regression algorithm. Then, two BLSs are adopted to approximate the optimal cost function and optimal control law, respectively. The connection weights of these two BLSs are updated using the given weights tuning law at each sampling instant. The proposed optimal controller is proved to ensure that all the system states and estimation errors are uniform ultimate bounded. Finally, simulation examples are carried out to further demonstrate the effectiveness of the proposed BLS-based approximator and optimal controller. [ABSTRACT FROM AUTHOR]

We consider decentralized large-scale continuous submodular constrained optimization problems over networks, where the goal is to maximize a sum of nonconvex functions with diminishing returns property. However, the computations of the projection step and the whole gradient can become prohibitive in high-dimensional constrained optimization problems. For this reason, a decentralized randomized block-coordinate Frank-Wolfe algorithm is proposed for submoduar maximization over networks by local communication and computation, which adopts the randomized block-coordinate descent and the Frank-Wolfe technique. We also show that the proposed algorithm converges to an approximation fact $(1-e^{-p_{\max }/p_{\min }})$ of the global maximal points at a rate of $\mathcal {O}(1/T)$ by choosing a suitable stepsize, where $T$ is the number of iterations. In addition, we confirm the theoretical results by experiments. [ABSTRACT FROM AUTHOR]

A variety of emergency events such as traffic accidents often happen in urban areas and the related emergency information needs to be urgently diffused to vehicles that may pass through the accident place to avoid escalation of the event. However, due to the dynamics of vehicles, the information diffusion links between vehicles and roadside units (RSUs) may be unstable, and thus the information diffusion based on fixed RSUs may lead to the low information propagation rate and the limited influence range. To address the above issues, we propose an emergency information diffusion strategy based on the Social Internet of Vehicle (SIoV), where vehicles can build inter-vehicle social relationships without human intervention and exchange emergency information through stable vehicle-to-vehicle (V2V) links. In detail, we design a $b$ -matching based stable link construction algorithm to build stable V2V links by considering the social characteristics and connection probability simultaneously, and then depict the vehicle link graph. Based on this graph, we formulate the information diffusion problem as an influence maximization problem. To solve this problem, we design an SIoV based emergency information influence maximization (SEIM) algorithm to maximize the influence range by selecting some influential seed vehicles and boosting some vehicles’ influence. The theoretical analysis and simulation results show that our algorithms have a lower dissemination delay and larger influence range by sacrificing part of the signaling overheads performance. [ABSTRACT FROM AUTHOR]

In this article, we propose a fast algorithm to generate a rank-minimized $\mathcal {H}^{2}$ -representation for solving electrically large volume integral equations (VIEs). Unlike existing methods whose complexity is as high as quadratic, the proposed algorithm has linearithmic complexity, and thus, it can handle problems with large electrical sizes. Furthermore, the algorithm is purely algebraic and kernel independent. Numerical experiments on electrically large 3-D arrays of dielectric cubes having over 33 million unknowns demonstrate the efficiency and accuracy of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Superconductive single-flux-quantum (SFQ) circuits operate with very high clock frequency and its timing design is a difficult task. In circuit design, static timing analysis (STA) is a key process for evaluating and verifying the timing of a circuit design. Conventional timing analysis for SFQ circuits focuses on circuits composed of clocked gates and splitters; however, practical SFQ circuits are composed of various gates, i.e., not only clocked gates but also other gates, such as nondestructive read-out, confluence buffer, and clockless logic gates. In this article, to express timing constraints of both clocked gate cells and other cells, we define timing requirements of cells as minimum and maximum acceptable intervals on ordered pairs of input pins. Via these, we express timing constraints of cells in an SFQ circuit design. Furthermore, to eliminate unnecessary pessimism during variation-aware timing analysis, we propose a method of common path pessimism removal (CPPR) for SFQ circuits composed of various cells. We implement an STA tool using the defined timing constraints and the CPPR method. The experimental results show that our STA tool verifies the timing of SFQ circuits composed of various cells. [ABSTRACT FROM AUTHOR]

Emerging applications with low-latency requirements such as real-time analytics, immersive media applications, and intelligent virtual assistants have rendered Edge Computing as a critical computing infrastructure. Existing studies have explored the cloudlet placement problem in a homogeneous scenario with different goals such as latency minimization, load balancing, energy efficiency, and placement cost minimization. However, placing cloudlets in a highly heterogeneous deployment scenario considering the next-generation 5G networks and IoT applications is still an open challenge. The novel requirements of these applications indicate that there is still a gap in ensuring low-latency service guarantees when deploying cloudlets. Furthermore, deploying cloudlets in a cost-effective manner and ensuring full coverage for all users in edge computing are other critical conflicting issues. In this article, we address these issues by designing a bifactor approximation algorithm to solve the heterogeneous cloudlet placement problem to guarantee a bounded latency and placement cost, while fully mapping user applications to appropriate cloudlets. We first formulate the problem as a multi-objective integer programming model and show that it is a computationally NP-hard problem. We then propose a bifactor approximation algorithm, ACP, to tackle its intractability. We investigate the effectiveness of ACP by performing extensive theoretical analysis and experiments on multiple deployment scenarios based on New York City OpenData. We prove that ACP provides a (2,4)-approximation ratio for the latency and the placement cost. The experimental results show that ACP obtains near-optimal results in a polynomial running time making it suitable for both short-term and long-term cloudlet placement in heterogeneous deployment scenarios. [ABSTRACT FROM AUTHOR]

Outlier detection is one of the most important research directions in data mining. However, most of the current research focuses on outlier detection for categorical or numerical attribute data. There are few studies on the outlier detection of mixed attribute data. In this article, we introduce fuzzy rough sets (FRSs) to deal with the problem of outlier detection in mixed attribute data. Since the outlier detection model of the classical rough set is only applicable to the categorical attribute data, we use FRS to generalize the outlier detection model and construct a generalized outlier detection model based on fuzzy rough granules. First, the granule outlier degree (GOD) is defined to characterize the outlier degree of fuzzy rough granules by employing the fuzzy approximation accuracy. Then, the outlier factor based on fuzzy rough granules is constructed by integrating the GOD and the corresponding weights to characterize the outlier degree of objects. Furthermore, the corresponding fuzzy rough granules-based outlier detection (FRGOD) algorithm is designed. The effectiveness of the FRGOD algorithm is evaluated through experiments on 16 real-world datasets. The experimental results show that the algorithm is more flexible for detecting outliers and is suitable for numerical, categorical, and mixed attribute data. [ABSTRACT FROM AUTHOR]

Network slicing is a promising approach for enabling low latency computation offloading in edge computing systems. In this paper, we consider an edge computing system under network slicing in which the wireless devices generate latency sensitive computational tasks. We address the problem of joint dynamic assignment of computational tasks to slices, management of radio resources across slices and management of radio and computing resources within slices. We formulate the Joint Slice Selection and Edge Resource Management (JSS-ERM) problem as a mixed-integer problem with the objective to minimize the completion time of computational tasks. We show that the JSS-ERM problem is NP-hard and develop an approximation algorithm with bounded approximation ratio based on a game theoretic treatment of the problem. We use extensive simulations to provide insight into the performance of the proposed solution from the perspective of the whole system and from the perspective of individual slices. Our results show that the proposed slicing policy can achieve significant gains compared to the equal slicing policy, and that the computational complexity of the proposed task placement algorithm is approximately linear in the number of devices. [ABSTRACT FROM AUTHOR]

Emerging communication technologies allow to reconfigure the physical network topology at runtime, enabling demand-aware networks (DANs): networks whose topology is optimized toward the workload they serve. However, today, only little is known about the fundamental algorithmic problems underlying the design of such demand-aware networks. This paper presents the first bounded-degree, demand-aware network, $\textit {cl-DAN} $ , which minimizes both congestion and route lengths. The degree bound $\Delta $ is given as part of the input. The designed network is provably (asymptotically) optimal in each dimension individually: we show that there do not exist any bounded-degree networks providing shorter routes (independently of the load), nor do there exist networks providing lower loads (independently of the route lengths). The main building block of the designed $\textit {cl-DAN} $ networks are $\textit {ego-trees}$ : communication sources arrange their communication partners in an optimal tree, individually. While the union of these ego-trees forms the basic structure of $\textit {cl-DANs}$ , further techniques are presented to ensure bounded degrees (for scalability). [ABSTRACT FROM AUTHOR]

This work proposes linear time strategies to optimally configure the phase shifts for the reflective elements of an intelligent reflecting surface (IRS). Specifically, we show that the binary phase beamforming can be optimally solved in linear time to maximize the received signal-to-noise ratio (SNR). For the general $K$ -ary phase beamforming, we develop a linear time approximation algorithm that guarantees performance within a constant fraction $(1+\cos (\pi /K))/2$ of the global optimum, e.g., it can attain over 85% of the optimal performance for the quadrature beamforming with $K=4$. According to the numerical results, the proposed approximation algorithm for discrete IRS beamforming outperforms the existing algorithms significantly in boosting the received SNR. [ABSTRACT FROM AUTHOR]

In the context of wireless sensor networks (WSNs), the problem of virtual backbones (VBs) for undertaking routing tasks to alleviate broadcast storms has been extensively studied. In practical applications, different nodes in a WSN may have different transmission ranges because of differences in power control or functionality, among other reasons. In such a situation, a disk graph (DG) can be used as a mathematical model of the WSN, and a strongly connected dominating and absorbent set (SCDAS) in the DG can be treated as a VB in the corresponding WSN. In a WSN with faulty nodes, a fault-tolerant VB is superior to a traditional one. Thus, it is desirable to construct a $ k$ k -strongly connected $ m$ m -dominating and absorbent set ($ (k,m)$ (k , m) -SCDAS) in the DG to serve as a fault-tolerant VB in the corresponding WSN. In this article, to enable the construction of a high-quality $ (k,m)$ (k , m) -SCDAS in a DG, a constant approximation algorithm with a performance ratio of $(2k(5^{k-1}-1)+1)(R+m+4(\frac{R}{m}+1))$ (2 k (5 k - 1 - 1) + 1) (R + m + 4 (R m + 1)) is proposed, where $ k$ k and $ m$ m are constants ($ 2 \;\leqslant\; k \;\leqslant\; m$ 2 ⩽ k ⩽ m ) and $ R$ R is the maximum number of independent nodes within the transmission range of a node in the DG. A theoretical analysis and simulation results show that our work is superior to previous approaches. [ABSTRACT FROM AUTHOR]

Emerging virtual network functions (VNFs) bring new opportunities to network services on the edge within customers’ premises. Network services are realized by chained up VNFs, which are called service function chains (SFCs). These services are deployed on commercial edge servers for higher flexibility and scalability. Despite such promises, it is still unclear how to provide highly available and cost-effective SFCs under edge resource limitations and time-varying VNF failures. In this paper, we propose a novel Reliability-aware Adaptive Deployment scheme named RAD to efficiently place and back up SFCs over both the edge and the cloud. Specifically, RAD first deploys SFCs to fully utilize edge resources. It then uses both static backups and dynamic ones created on the fly to guarantee the availability under the resource limitation of edge networks. RAD does not assume failure rates of VNFs but instead strives to find the sweet spot between the desired availability of SFCs and the backup cost. Theoretical performance bounds, extensive simulations, and small-scale experiments highlight that RAD provides significantly higher availability with lower backup costs compared with existing baselines. [ABSTRACT FROM AUTHOR]

Under the paradigm of edge computing, the enormous data generated at the network edge can be processed locally. To make full utilization of these widely distributed data, we focus on an edge computing system that conducts distributed machine learning using gradient-descent based approaches. To ensure the system’s performance, there are two major challenges: how to collect data from multiple data source nodes for training jobs and how to allocate the limited resources on each edge server among these jobs. In this paper, we jointly consider the two challenges for distributed training (without service requirement), aiming to maximize the system throughput while ensuring the system’s quality of service (QoS). Specifically, we formulate the joint problem as a mixed-integer non-linear program, which is NP-hard, and propose an efficient approximation algorithm. Furthermore, we take service placement into consideration for diverse training jobs and propose an approximation algorithm. We also analyze that our proposed algorithm can achieve the constant bipartite approximation under many practical situations. We build a test-bed to evaluate the effectiveness of our proposed algorithm in a practical scenario. Extensive simulation results and testing results show that the proposed algorithms can improve the system throughput 56-69 percent compared with the conventional algorithms. [ABSTRACT FROM AUTHOR]

Subset selection plays an important role in the field of evolutionary multiobjective optimization (EMO). Especially, in an EMO algorithm with an unbounded external archive (UEA), subset selection is an essential post-processing procedure to select a prespecified number of solutions as the final result. In this article, we discuss the efficiency of greedy subset selection for the hypervolume, inverted generational distance (IGD), and IGD plus (IGD+) indicators. Greedy algorithms usually efficiently handle the subset selection. However, when a large number of solutions are given (e.g., subset selection from tens of thousands of solutions in a UEA), they often become time consuming. Our idea is to use the submodular property, which is known for the hypervolume indicator, to improve their efficiency. First, we prove that the IGD and IGD+ indicators are also submodular. Next, based on the submodular property, we propose an efficient greedy inclusion algorithm for each indicator. We demonstrate through computational experiments that the proposed algorithms are much faster than the standard greedy subset selection algorithms. The proposed algorithms also help the research on performance indicators. [ABSTRACT FROM AUTHOR]

5G communication network is vital to the intelligent and unmanned technology of open-pit mine, but the high cost of 5G base station deployment will bring huge cost increases to mining enterprises. Thus, this article proposes an improved sparrow search algorithm (SSA) using random walk strategy (RWSSA) to optimization the distribution and signal coverage of 5G base stations in open-pit mine. In order to verify the performance of the algorithm, the SSA, the modified ant lion optimizer, the particle swarm optimization, and the RWSSA were used to compare and analyze the accuracy and speed of the algorithm in solving high dimensionality benchmark functions, respectively. The dimensions used in the test are 30, 100, and 500 dimensions. After that, four algorithms were applied to a real example to optimize the deployment of 5G base stations, including macrobase stations and microbase stations. RWSSA has very good performance in terms of performance and practical application. Therefore, RWSSA is more suitable for the application of 5G base station distribution optimization in open-pit mines. [ABSTRACT FROM AUTHOR]

There is an increasing need for charging station recommendation to minimize the overall charging time for electric vehicles and balance load for the charging stations. To grant this need, we model the recommendation problem as a Markov Decision Process (MDP) problem. However, the traditional MDP model has the issue of ‘curse of dimensionality’. To address this issue, we propose an extension of MDP: multiple-phase MDP, in which the state transition of MDP is decomposing into several phases, so as to reduce the state space and state transition complexities. This is done by introducing two states other than the normal state defined in MDP: post decision state and intermediate decision state. Then, we propose an online learning based algorithm to solve the formulated multiple-phase MDP model. Thanks to the reduced complexities of the state space and state transition, the proposed online algorithm can converge fast. By comparing to other recommendation mechanisms, such as game theory based recommendation and Q-learning based recommendation, our simulation evaluation demonstrates that our proposition can bring good performance. [ABSTRACT FROM AUTHOR]

The paper presents research on mode identification of broad-band oscillation in interconnected power system. A data-driven mode identification (DDMI) method for broad-band oscillation signals is proposed creatively in this paper. Firstly, piecewise aggregation approximation algorithm is improved to achieve effective dimension reduction of oscillation data. Combined with ${k}$ -Shape clustering algorithm, oscillation database is established with historical data, real-time data and simulation data. Then, oscillation mode identification models corresponding to different data categories can be obtained based on random forest algorithm, which can realize fast and automatic matching between broad-band oscillation data and oscillation mode parameters. Finally, the identification results of two simulation oscillation cases and an actual oscillation case show that proposed method can accurately identify the oscillation mode parameters from broad-band oscillation signals and has higher accuracy compared with other methods. [ABSTRACT FROM AUTHOR]

Feature evaluation is an important issue in constructing a feature selection algorithm in kernelized fuzzy rough sets, which has been proven to be an effective approach to deal with nonlinear classification tasks and uncertainty in learning problems. However, the feature evaluation function developed with kernelized fuzzy rough sets cannot better reflect the affinity relationship of samples and is time-consuming. To overcome these drawbacks, in this article, the problem of feature selection with kernelized fuzzy rough sets is studied based on the spectral graph theory. First, the within-class and between-class sample similarity matrices by using kernelized fuzzy approximation operators are constructed. Two operators, which can capture the affinity relationship of samples, are then introduced based on the sample similarity matrices. The proposed operator can be regarded as the sum of the weighted kernelized fuzzy approximation operators. Second, based on the ratio criterion, a feature evaluation function and its corresponding feature selection algorithm FRKF are presented, which can effectively evaluate the importance of features. Third, to illustrate the performance of the proposed algorithm, extensive experiments have been carried out to compare FRKF and other well-known feature selection methods, including the feature ranking methods and feature subset selection methods on various classification tasks. The experimental results on real-world datasets demonstrate that FRKF achieves the high performances in terms of the robustness, efficiency, and effectiveness. [ABSTRACT FROM AUTHOR]

Seismic prediction of natural fractures is essential for the characterization of unconventional reservoirs because fractures provide seepage paths for fluid migration and storage space for hydrocarbon accumulation. However, it remains challenging to robustly estimate anisotropic parameters for fracture characterization based on seismic inversion methods. We propose an improved inversion scheme for the robust and accurate estimation of anisotropic parameters using PP-wave azimuthal amplitude differences incorporated with a hybrid optimization algorithm. Modeling analysis indicates that by removing the effect of isotropic terms, azimuthal amplitude differences are more sensitive to anisotropic parameters than the traditional azimuthal reflection coefficient; this can avoid possible instabilities in anisotropic parameter estimates that may occur in conventional methods due to unbalanced weighting coefficients between isotropic and anisotropic terms. Meanwhile, the proposed hybrid algorithm takes advantage of the global optimization ability of the simulated annealing algorithm and the fast convergence characteristics of the particle swarm optimization algorithm. Synthetic data tests indicate that the hybrid algorithm achieves reliable and stable estimates of anisotropic parameters with higher computational accuracy and efficiency than traditional methods. The improved inversion method is applied to characterize fractures in volcanic gas reservoirs. Based on azimuthal amplitude differences obtained after estimating fracture orientation using the Fourier series method, anisotropic parameters are computed and converted to weakness properties, which is more meaningful in terms of the fracture properties. Our results indicate that the obtained fracture tangential weakness exhibits an apparent correspondence with well-log permeability, thus justifying the applicability of the proposed method for fracture prediction. [ABSTRACT FROM AUTHOR]

Reconfigurable intelligent surfaces (RISs) have been recently considered as a promising candidate for energy-efficient solutions in future wireless networks. Their dynamic and low-power configuration enables coverage extension, massive connectivity, and low-latency communications. Due to a large number of unknown variables referring to the RIS unit elements and the transmitted signals, channel estimation and signal recovery in RIS-based systems are the ones of the most critical technical challenges. To address this problem, we focus on the RIS-assisted wireless communication system and present two joint channel estimation and signal recovery schemes based on message passing algorithms in this paper. Specifically, the proposed bidirectional scheme applies the Taylor series expansion and Gaussian approximation to simplify the sum-product procedure in the formulated problem. In addition, the inner iteration that adopts two variants of approximate message passing algorithms is incorporated to ensure robustness and convergence. Two ambiguities removal methods are also discussed in this paper. Our simulation results show that the proposed schemes show the superiority over the state-of-art benchmark method. We also provide insights on the impact of different RIS parameter settings on the proposed schemes. [ABSTRACT FROM AUTHOR]

Constructing effective priors is critical to solving ill-posed inverse problems in image processing and computational imaging. Recent works focused on exploiting non-local similarity by grouping similar patches for image modeling, and demonstrated state-of-the-art results in many image restoration applications. However, compared to classic methods based on filtering or sparsity, non-local algorithms are more time-consuming, mainly due to the highly inefficient block matching step, i.e., distance between every pair of overlapping patches needs to be computed. In this work, we propose a novel Self-Convolution operator to exploit image non-local properties in a unified framework. We prove that the proposed Self-Convolution based formulation can generalize the commonly-used non-local modeling methods, as well as produce results equivalent to standard methods, but with much cheaper computation. Furthermore, by applying Self-Convolution, we propose an effective multi-modality image restoration scheme, which is much more efficient than conventional block matching for non-local modeling. Experimental results demonstrate that (1) Self-Convolution with fast Fourier transform implementation can significantly speed up most of the popular non-local image restoration algorithms, with two-fold to nine-fold faster block matching, and (2) the proposed online multi-modality image restoration scheme achieves superior denoising results than competing methods in both efficiency and effectiveness on RGB-NIR images. The code for this work is publicly available at https://github.com/GuoLanqing/Self-Convolution. [ABSTRACT FROM AUTHOR]

Existing research on finding social groups mostly focuses on dense subgraphs in social networks. However, finding socially tenuous groups also has many important applications. In this article, we introduce the notion of $k$ k -triangles to measure the tenuity of a group. We then formulate a new research problem, Minimum $k$ k -Triangle Disconnected Group with No-Pair Constraint (MkTG), to find a socially tenuous group from the online social network. We prove that MkTG is NP-hard and inapproximable within any ratio. Two algorithms, namely TERA and TERA-ADV, are designed for solving MkTG effectively and efficiently. Further, we examine the MkTG problem on tree-based social networks, due to their structural resemblance with corporate social networks built upon the supervision relation. Accordingly, we devise an efficient algorithm, namely Tenuity Maximization for Trees (TMT), to obtain the optimal solution in polynomial time. In addition, we study a more general version of MkTG, named Generalized Minimum $k$ k -Triangle Disconnected Group without No-Pair Constraint (MkTG-G). We formulate MkTG-G, analyze its inapproximability, and propose a randomized approximation algorithm, named Randomized Ranking with Limited Neighborhood Participation (RLNP). Experimental results on real datasets manifest that the proposed algorithms outperform the baselines in terms of both efficiency and solution quality. [ABSTRACT FROM AUTHOR]

Static and dynamic clustering algorithms are a fundamental tool in any machine learning library. Most of the efforts in developing dynamic machine learning and data mining algorithms have been focusing on the sliding window model or more simplistic models. However, in many real-world applications one might need to deal with arbitrary deletions and insertions. For example, one might need to remove data items that are not necessarily the oldest ones, because they have been flagged as containing inappropriate content or due to privacy concerns. Clustering trajectory data might also require to deal with more general update operations. We develop a $(2+\epsilon)$ (2 + ε) -approximation algorithm for the $k$ k -center clustering problem with “small” amortized cost under the fully dynamic adversarial model. In such a model, points can be added or removed arbitrarily, provided that the adversary does not have access to the random choices of our algorithm. The amortized cost of our algorithm is poly-logarithmic when the ratio between the maximum and minimum distance between any two points in input is bounded by a polynomial, while $k$ k and $\epsilon$ ε are constant. Furthermore, we significantly improve the memory requirement of our fully dynamic algorithm, although at the cost of a worse approximation ratio of $4 +\epsilon$ 4 + ε . Our theoretical results are complemented with an extensive experimental evaluation on dynamic data from Twitter, Flickr, as well as trajectory data, demonstrating the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

The Recently proposed Vector Approximate Message Passing (VAMP) algorithm demonstrates a great reconstruction potential at solving compressed sensing related linear inverse problems. VAMP provides high per-iteration improvement, can utilize powerful denoisers like BM3D, has rigorously defined dynamics and is able to recover signals measured by highly undersampled and ill-conditioned linear operators. Yet, its applicability is limited to relatively small problem sizes due to the necessity to compute the expensive LMMSE estimator at each iteration. In this work we consider the problem of upscaling VAMP by utilizing Conjugate Gradient (CG) to approximate the intractable LMMSE estimator. We propose a rigorous method for correcting and tuning CG withing CG-VAMP to achieve a stable and efficient reconstruction. To further improve the performance of CG-VAMP, we design a warm-starting scheme for CG and develop theoretical models for the Onsager correction and the State Evolution of Warm-Started CG-VAMP (WS-CG-VAMP). Additionally, we develop robust and accurate methods for implementing the WS-CG-VAMP algorithm. The numerical experiments on large-scale image reconstruction problems demonstrate that WS-CG-VAMP requires much fewer CG iterations compared to CG-VAMP to achieve the same or superior level of reconstruction. [ABSTRACT FROM AUTHOR]

In this paper, we investigate non-orthogonal multiple access (NOMA) assisted secure computation offloading under the eavesdropping-attack, in which a malicious node overhears the edge-computing user's (EU’s) offloading transmission to the edge-computing server (ES), and NOMA is used for the EU's offloading and meanwhile for providing artificial jamming to the eavesdropper. Since multi-user simultaneous transmission over a same frequency channel can be enabled by NOMA, a wireless user (WU) can form a NOMA pair with the EU to provide cooperative jamming to the eavesdropper while also gaining an opportunity of sending its data. Focusing on the EU-WU pair with the fixed WU's energy-provisioning, we exploit the physical layer security to quantify the EU's offloading throughput with the help of WU's jamming. We then study the joint optimization of the EU's computation offloading and the EU-WU's NOMA transmission for minimizing the EU's total energy consumption subject to its latency-requirement in completing the computation-task. By utilizing the feature of analytical solution of the WU's transmission, we then investigate the WU's optimal energy-provisioning for the EU-WU pair, such that both the EU and WU can benefit from the cooperative jamming in a fairness manner. Specifically, we formulate the EU-WU's cooperation as a Nash bargaining game. By identifying the monotonic feature of Nash bargaining problem, we propose a polyblock approximation based algorithm for determining the WU's optimal energy-provisioning to achieve the win-win solution for the paired EU and WU. Finally, we investigate the scenario of multiple EUs and WUs, and aim at finding the stable pairing between the EUs and WUs, such that no individual EU (or WU) would like to change its partner. An efficient algorithm, which is based on the Gale-Shapley theory while exploiting the quantitative feature of EUs’ and WUs’ net-rewards, is proposed to achieve the stable EU-WU pairings. Numerical results are provided to validate our proposed algorithms and demonstrate the advantage of our proposed NOMA assisted computation offloading via cooperative jamming. [ABSTRACT FROM AUTHOR]

In this paper, we propose one joint interference alignment and subchannel allocation (JIARA) interference management scheme, aiming at maximizing the number of satisfactory users with different degrees of freedom (DoF) demand in ultra-dense wireless networks, while the existing works only consider the same DoF demands. The original JIARA scheme is equivalent to the maximum $K$ -colorable subgraph (MKCS) problem in graph theory for a given $K$ -colors and the multicoloring demand at each vertex, hence NP-hard. Therefore, we propose one graph theory based low complexity sub-optimal JIARA scheme. Firstly, we propose one virtual allocation of subchannel based scheme to construct transformed the conflict graph, which is applicable for the different DoF demands and different size of the feasible IA group. Furthermore, we propose one greedy multi-coloring based algorithm to determine the maximum number of satisfactory users. Simulation results show that the proposed JIARA scheme outperforms the subchannel resource allocation only scheme. [ABSTRACT FROM AUTHOR]

A new method extending the scope of the superalgebraically convergent 2-D wave diffraction algorithms is proposed. The principal tool is the construction of an infinitely smooth approximation to the boundary contour. The construction is based on the ideas of Tikhonov’s regularization to the stable summation of the Fourier series and the evaluation of unbounded operators. Both the algorithms for smoothing and the nonsaturated solutions for integral equations together provide the superalgebraic (faster than any algebraic) convergence. The comparison of the algorithms using the original (noninfinitely smooth) parameterization and the infinitely smooth one demonstrates the essential advantage of the latter over the former with respect to accuracy and time consumption. [ABSTRACT FROM AUTHOR]

A new approach is proposed for the planar array failure diagnosis from a set of far-field measurements. Under the framework of Bayesian learning, a Bernoulli–Gaussian (BG) model is constructed to exploit the binary prior information of the unknown failure elements. Subsequently, the variational expectation maximization (EM) strategy is used to perform the Bayesian inference. Moreover, the damped generalized approximate message passing (GAMP) is further adopted to circumvent the matrix inversion in the variational EM procedure, thus making the overall process computationally very efficient. A set of representative numerical experiments are provided to validate the accuracy, efficiency, and flexibility of the proposed method. [ABSTRACT FROM AUTHOR]

We study the resilient scheduling of moldable parallel jobs on high-performance computing (HPC) platforms. Moldable jobs allow for choosing a processor allocation before execution, and their execution time obeys various speedup models. The objective is to minimize the overall completion time or the makespan, when jobs can fail due to silent errors and hence may need to be re-executed after each failure until successful completion. Our work generalizes the classical scheduling framework for failure-free jobs. To cope with silent errors, we introduce two resilient scheduling algorithms, Lpa-List and Batch-List, both of which use the List strategy to schedule the jobs. Without knowing a priori how many times each job will fail, Lpa-List relies on a local strategy to allocate processors to the jobs, while Batch-List schedules the jobs in batches and allows only a restricted number of failures per job in each batch. We prove approximation ratios for the two algorithms under several prominent speedup models (e.g., roofline, communication, Amdahl, power, monotonic, and a mix model). An extensive set of simulations is conducted to evaluate different variants of the two algorithms, and the results show that they consistently outperform some baseline heuristics. Overall, our best algorithm is within a factor of 1.6 of a lower bound on average over the entire set of experiments, and within a factor of 4.2 in the worst case. [ABSTRACT FROM AUTHOR]

In this paper, we study the employment of multiple Unmanned Aerial Vehicles (UAVs) to monitor Points of Interests (PoIs) in a disaster area, e.g., collapsed buildings after an earthquake, where the UAVs can take photos and videos for the people trapped at PoIs, because such valuable information is imperative to make rescue decisions. Unlike most existing studies that ignored the monitoring time of PoIs and simply minimized the longest flying distance among the UAVs, we observe that it takes time to monitor the PoIs. Then, it is possible that the flying distance of a UAV in its flying tour may not be too long, the tour however contains many densely-located PoIs. Therefore, it will take a very long time for the UAV to monitor the PoIs in its tour. In this paper, we first formulate a problem of finding flying tours for $K$ K given UAVs to collaboratively monitor PoIs in a disaster area, such that the maximum spent time of the $K$ K UAVs among their tours is minimized, where the spent time of a UAV in its tour consists of the flying time and the PoI monitoring time. We then propose a novel $5\frac{1}{3}$ 5 1 3 -approximation algorithm for the problem, improving the best approximation ratio 6 so far for the problem of minimizing the longest flying distance among the UAVs. In addition, we extend the proposed algorithm to the case that each UAV may not be able to monitor all PoIs assigned to it, due to its limited maximum flying time (e.g., 30 minutes), and the UAV must return to its depot to replace its battery. We finally evaluate the performance of the proposed algorithms via simulation environments, and experimental results show that the proposed algorithms are very promising. Especially, the maximum spent times of the $K$ K UAVs in their tours by the proposed algorithms are up to 30 percent shorter than those by existing algorithms. In addition, the empirical approximation ratios of the proposed algorithms are no more than 2.4, which are much smaller than their theoretical approximation ratios that are at least $5\frac{1}{3}$ 5 1 3 . [ABSTRACT FROM AUTHOR]

Homomorphic encryption (HE) is being widely used for privacy-preserving computation. Since HE schemes only support polynomial operations, it is prevalent to use polynomial approximations of non-polynomial functions. We cannot monitor the intermediate values during the homomorphic evaluation; as a consequence, we should utilize polynomial approximations with sufficiently large approximation intervals to prevent the failure of the evaluation. However, the large approximation interval potentially accompanies computational overheads, and it is a serious bottleneck of HE application on real-world data. In this work, we introduce domain extension polynomials (DEPs) that extend the domain interval of functions by a factor of $k$ while preserving the feature of the original function on its original domain interval. By repeatedly iterating the domain-extension process with DEPs, we can extend with $O(\log {K})$ operations the domain of a given function by a factor of $K$ while the feature of the original function is preserved in its original domain interval. By using DEPs, we can efficiently evaluate in an encrypted state a function that converges at infinities, i.e., $\lim _{x\to \infty }f(x)$ and $\lim _{x\to -\infty }f(x)$ exist in $\mathbb {R}$. To uniformly approximate the function on $[-R,R]$ , our method exploits $O(\log {R})$ operations and $O(1)$ memory. This is more efficient than the previous approach, the minimax approximation and Paterson-Stockmeyer algorithm, which uses $\Omega (\sqrt {R})$ multiplications and $\Omega (\sqrt {R})$ memory for the evaluation. As another application of DEPs, we also suggest a method to manage the risky outliers from a large interval $[-R,R]$ by using $O(\log {R})$ additional multiplications. As a real-world application, we trained the logistic regression classifier on large public datasets in an encrypted state by using our method. We exploit our method to the evaluation of the logistic function on large intervals, e.g., [−7683, 7683]. [ABSTRACT FROM AUTHOR]

Many problems in industrial smart manufacturing, such as process operational optimization and decision-making, can be regarded as distributed nonconvex optimization problems, whose goal is to utilize distributed nodes to cooperatively search for the minimal value of the global objective function. With the consideration of data transmission mode, transmission condition, and communication waste in industrial applications, it is meaningful to study the distributed nonconvex optimization problem with an event-triggered strategy over time-varying directed networks. To solve such a problem, a distributed nonconvex event-triggered algorithm is proposed in this article. Under some assumptions on local objective functions, gradients, and step sizes, the convergence of the proposed event-triggered algorithm to the local minimum is established theoretically. Moreover, it is obtained that the proposed distributed event-triggered algorithm has a convergence rate of $O(1/\ln (t))$. Finally, two examples of industrial systems are provided to validate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this letter, to improve the performance of the space-time adaptive processing (STAP) filter with finite training samples, a novel algorithm with multiple measurement vectors (MMV) based on sparse recovery (SR) is proposed. Compared with traditional SR STAP algorithms, we utilize the knowledge of Capon spectrum to design a weighted ${\ell }_2{\rm{ - norm}}$ penalty which can better approximate the original ${\ell }_0{\rm{ - norm}}$. Besides, the proposed algorithm has fast convergence performance and closed-form analytic solution in each iteration. Simulation results demonstrate the effectiveness and great performance of the proposed method. [ABSTRACT FROM AUTHOR]

The success of online shopping accelerates the development of express delivery business with economic and efficient service. Current express delivery systems usually deliver the packages in noncooperation mode and cannot jointly optimize the express fee and moving cost of users. This paper proposes the cooperative package assignment system by lumping packages at the same express station to share the express fee, and proposes a novel pricing structure to stimulate the express stations to join the system without revenue loss by introducing cooperation cost. We formulate the cooperative package assignment (CPA) problem with heterogeneous express stations for joint optimization of users’ express fee and moving cost. Then, an approximate algorithm, CPAA, is proposed for the CPA problem based on the greedy approach using submodular function minimization. We show that the designed algorithm achieves computational efficiency and guaranteed approximation. Furthermore, we model the large-scale CPA problem as CPA-game and present a game theoretic algorithm, CPAGA. We show that CPA-game has at least one Nash Equilibrium, and CPAGA finally converges to a pure Nash Equilibrium. Through extensive simulations, we demonstrate that CPAA and CPAGA show great advantages in terms of comprehensive cost, which is 28.1% and 19.9% lower than that in noncooperation mode on average, respectively. Moreover, CPAGA shows great scalability and is more suitable for large-scale cooperative package assignment systems. [ABSTRACT FROM AUTHOR]

This paper investigates the idea of introducing learning algorithms into parking guidance and information systems that employ a central server, in order to provide estimated optimal parking searching strategies to travelers. The parking searching process on a network with uncertain parking availability can naturally be modeled as a Markov Decision Process (MDP). Such an MDP with full information can easily be solved by dynamic programming approaches. However, the probabilities of finding parking are difficult to define and calculate. Learning algorithms are suitable for addressing this issue. We propose an algorithm based on Q-learning, where a unique property of the parking searching MDP and the topology of the underlying transportation network are incorporated and utilized to improve its performance. This modification allows us to reduce the size of the learning problem dramatically, and thus the amount of data required to learn the optimal strategy. Numerical experiments conducted on a toy network with fixed parking probabilities show that the proposed learning algorithm outperforms the original Q-learning algorithm and three greedy heuristics in terms of the quality of the approximated optimal solution as well as the amount of training data required. Our numerical experiments on a real network with time-dependent underlying probabilities show that effective searching strategies can be achieved by the proposed algorithm, even though the learning algorithms treat the parking probabilities as constant during each exploration-exploitation cycle. The results again demonstrate that the proposed modified Q-learning algorithm significantly outperforms the original Q-learning with the same amount of training data. The results also provide insights into how the length and the split of the exploration-exploitation cycle affect the effectiveness of the proposed learning algorithm. [ABSTRACT FROM AUTHOR]

Scaffold filling is a critical step in DNA assembly. Its basic task is to fill the missing genes (fragments) into an incomplete genome (scaffold) to make it similar to the reference genome. There have been a lot of work under distinct measurements in the literature of genome comparison. For genomes with gene duplications, common string partition reveals the similarity more precisely, since it constructs a one-to-one correspondence between the same segments in the two genomes. In this paper, we adopt duo-preservation as the measurement, which is the complement of common string partition, i.e., the number of duo-preservations added to the number of common strings is exactly the length of a genome. Towards a proper scaffold filling, we just focus on the increased duo-preservations. This problem is called scaffold filling to maximize increased duo-preservations (abbr. SF-MIDP). We show that SF-MIDP is solvable in linear time for a simple version where all the genes of the scaffold are matched in a block-matching, but MAX SNP-complete for the general version, and cannot be approximated within $\frac{16263}{16262}$ 16263 16262 . Moreover, we present a basic approximation algorithm of factor 2, by which the optimal solution can be described in a new way, and then, improve the approximation factor to $\frac{12}{7}$ 12 7 via a greedy method. [ABSTRACT FROM AUTHOR]

Tandem repeats are repetitive structures present in some DNA sequences, consisting of many repeated copies of a single motif. They can serve as important markers for phylogenetic and population genetic studies, due to the high polymorphism in the number of motif copies as well as variations in the motif. The first step in using tandem repeats for phylogenetic studies is to estimate the evolutionary distance between a pair $D_1$ D 1 and $D_2$ D 2 of tandem repeat sequences with homologous motifs. This problem can be broken into two sub-problems: 1) Construct the most recent common ancestor of the sequences. 2) Calculate the evolutionary distance between each sequence and the hypothesised common ancestor. We present an algorithm that estimates the solution to the second problem. This takes the form of an asymmetric alignment algorithm to estimate the evolutionary distance between two tandem repeat sequences $A$ A and $D$ D , where $D$ D is assumed to have descended from $A$ A , under a model that allows block duplication, deletion, and variant substitution. The algorithm is asymmetric in the sense that the two input sequences $A$ A and $D$ D play different roles in the calculations, reflecting the assumption that $D$ D descends from $A$ A . Our model assumes static motif boundaries, meaning that motif duplication and deletion events must respect the motif boundaries. The algorithm may also be applied without modification to more complex repetitive structures with two or more motifs, such as nested tandem repeats. [ABSTRACT FROM AUTHOR]

This letter investigates reconfigurable intelligent surface (RIS)-assisted full-duplex multiple-input single-output wireless system, where the beamforming and RIS phase shifts are optimized to maximize the sum-rate for both single and distributed RIS deployment schemes. The preference of using the single or distributed RIS deployment scheme is investigated through three practical scenarios based on the links’ quality. The closed-form solution is derived to optimize the beamforming vectors and a novel deep reinforcement learning (DRL) algorithm is proposed to optimize the RIS phase shifts. Simulation results illustrate that the choice of the deployment scheme depends on the scenario and the links’ quality. It is further shown that the proposed algorithm significantly improves the sum-rate compared to the non-optimized scenario in both single and distributed RIS deployment schemes. Besides, the proposed beamforming derivation achieves a remarkable improvement compared to the approximated derivation in previous works. Finally, the complexity analysis confirms that the proposed DRL algorithm reduces the computation complexity compared to the DRL algorithm in the literature. [ABSTRACT FROM AUTHOR]

This paper proposes a real-time schedule model of a microgrid (MG) for maximizing battery energy storage (BES) utilization. To this end, a BES life model is linearized using piece-wise linearization and big-M method to assess the BES life loss (BLL) in a real-time manner. The cost-effective schedule model of the MG with multiple energy resources aims to maximize BES utilization while ensuring its sufficient lifespan. Corresponding to the optimization model, approximate dynamic programming (ADP) for maximizing BES utilization (ADP-MBU) in the real-time schedule is proposed to optimize the system under stochastic environments. In ADP-MBU, a new value function approximation method employing the BES cumulative life loss (BCLL) is developed to improve the optimality and applicability. The proposed ADP-MBU algorithm can achieve satisfactory approximate optimality while reflecting the variation of real-time BLL. Case studies validate the applicability of the proposed MG schedule model and the advantages of the proposed ADP-MBU algorithm. [ABSTRACT FROM AUTHOR]

Adaptive workflow management systems allow workflows to be changed in both the modeling and runtime stages, resulting in many workflow variants. Identifying a minimum sequence of high-level changes between two workflows represents a fundamental yet critical issue. The state-of-the-art approach utilizes digital logic to seek the optimal solution; however, this approach may face difficulties when advanced workflow patterns (e.g., loops) are involved, and it does not scale well. To address this problem, we first propose a naive approach that applies all valid changes to one workflow until the other workflow is found. Then, the approach is optimized from two aspects. First, we present advanced heuristics that significantly reduce the search space without pruning the optimal solution. Second, we employ the A $^\ast$ * search algorithm to direct the search procedure. Because the heuristic function used in the A $^\ast$ * algorithm is problem specific, we devise a consistent heuristic function to approximate the edit distance between two workflows, thereby accelerating the search. We implement our approach in a prototype tool and conduct extensive experiments on two data sets to evaluate its effectiveness and efficiency. The experimental results demonstrate that our approach outperforms the state of the art in terms of both application scope and scalability. [ABSTRACT FROM AUTHOR]

This article is concerned with the problem of computing the approximate preinverses of a fuzzy matrix with max-product composition. Employing the weighted $L_1$ distance, a variety of evaluation functions are defined according to the preselected weights, and then, an analytical method is proposed to determine all approximate preinverses of equal quality by minimizing the preselected evaluation function. Since only the approximate preinverses with fewer or preferably no zeros are acceptable for many practical applications, a criterion for selecting weights is established to ensure that the determined approximate preinverses are desirable. Some examples are given to illustrate our results. [ABSTRACT FROM AUTHOR]

Exponential functions are essential in many areas of science and engineering. Fast and efficient computing of such functions in multiple floating-point formats is a complex task for all classes of processing units—general purpose CPUs, digital signal processors, GPUs, intelligent processing units, and tensor processors (TPU)—developed recently for neural computing and deep machine learning. [ABSTRACT FROM AUTHOR]

Nonlinear precoding and pulse shaping are jointly considered in multi-user massive multiple-input multiple-output (MIMO) systems with low resolution D/A-converters (DACs) in terms of algorithmic approach as well as large system performance. Two design criteria are investigated: the mean squared error (MSE) with active constellation extension (ACE) and the symbol error rate (SER). Both formulations are solved based on a modified version of the generalized approximate message passing (GAMP) algorithm. Furthermore, theoretical performance results are derived based on the state evolution analysis of the GAMP algorithm. The MSE based technique is extended to jointly perform over-the-air (OTA) spectral shaping and precoding for frequency-selective channels, in which the spectral performance is characterized at the transmitter and at the receiver. Simulation and analytical results demonstrate that the MSE based approach yields the same performance as the SER based formulation in terms of uncoded SER. The analytical results provide good performance predictions up to medium SNR. Substantial improvements in detection, as well as spectral performance, are obtained from the proposed combined pulse shaping and precoding approach compared to standard linear methods. [ABSTRACT FROM AUTHOR]

In this paper, we investigate an intelligent reflecting surface (IRS) assisted multi-user multiple-input multiple-output (MIMO) full-duplex (FD) system. We jointly optimize the active beamforming matrices at the access point (AP) and uplink users, and the passive beamforming matrix at the IRS to maximize the weighted sum-rate of the system. Since it is practically difficult to acquire the channel state information (CSI) for IRS-related links due to its passive operation and large number of elements, we conceive a mixed-timescale beamforming scheme. Specifically, the high-dimensional passive beamforming matrix at the IRS is updated based on the channel statistics while the active beamforming matrices are optimized relied on the low-dimensional real-time effective CSI at each time slot. We propose an efficient stochastic successive convex approximation (SSCA)-based algorithm for jointly designing the active and passive beamforming matrices. Moreover, due to the high computational complexity caused by the matrix inversion computation in the SSCA-based optimization algorithm, we further develop a deep-unfolding neural network (NN) to address this issue. The proposed deep-unfolding NN maintains the structure of the SSCA-based algorithm but introduces a novel non-linear activation function and some learnable parameters induced by the first-order Taylor expansion to approximate the matrix inversion. In addition, we develop a black-box NN as a benchmark. Simulation results show that the proposed mixed-timescale algorithm outperforms the existing single-timescale algorithm and the proposed deep-unfolding NN approaches the performance of the SSCA-based algorithm with much reduced computational complexity when deployed online. [ABSTRACT FROM AUTHOR]

A new four-dimensional (4D) probabilistically shaped (PS) ultra-high order modulation format is proposed with pilot aided carrier phase recovery (PA-CPR) algorithm to improve the general mutual information (GMI) performance. While the structure of the 4D-PS ultra-high order modulation format uses constellation set partitioning (SP) based on amplitude translation, and the PA-CPR applies 8-level amplitude phase shift keying (8APSK) pilot. To demonstrate the feasibility of the scheme, the PS-1024QAM system is designed on the simulation platform. The results show that the proposed 8APSK-PA-CPR algorithm outperforms the QPSK-PA-CPR algorithm. The gain of the optimal 8APSK-PA-CPR is ∼0.4 dB compared with the quadrature phase-shift keying (QPSK) PA-CPR algorithm. The steep drop of blind phase search (BPS) with different PS factors is overcome by 8APSK-PA-CPR when the signal-to-noise (SNR) ratio is lower than 24 dB. The maximum improvement of GMI is 1.3 bit/symbol when the SNR is higher than 26 dB and the complexity of the 8APSK-PA-CPR algorithm is reduced by 99.9% compared with the BPS algorithm. The gain obtained from the proposed 4D modulation scheme is ∼2.8 dB under the condition of GMI = 17.7971 bit/symbol. It demonstrated that this scheme has a strong tolerance to noise, low computational complexity, and high coding gain. It is a feasible and flexible scheme for PS high-order modulation format transmission systems. [ABSTRACT FROM AUTHOR]

Compressed sensing (CS)-based synthetic aperture radar (SAR) imaging methods are showing superior potential in imaging performance over classical matched filtering-based methods. However, the CS-based methods require much more computational cost to solve the iterative optimization composed of large-scale matrix operators. To hold the improvement of imaging performance and reduce the computational cost, in this article, we propose a novel SAR imaging method by a deep unfolded network (DUN) of an iterative shrinkage threshold algorithm (ISTA) with the approximated observation of a range-Doppler algorithm (RDA) operator. The proposed method takes the radar echoes as the input to learn the imaging procedure. First, the approximated observation is utilized in an SAR imaging model to reduce the size of the DUN. Moreover, we use ISTA as an example to introduce how to establish DUN with approximated observation, in which the detailed structure to handle the complex-valued radar echoes is also designed. Finally, the autoencoder is utilized to calculate the difference of the echoes rather than the imaging results, so that we can train the proposed network by unsupervised learning. The experiments of point targets, surface targets, and real scenes show that the proposed imaging method is superior in terms of imaging performance and computing efficiency. [ABSTRACT FROM AUTHOR]

We propose a ParametRIc MAnifold Learning (PRIMAL) algorithm for Gaussian mixtures models (GMM), assuming that GMMs lie on or near to a manifold of probability distributions that is generated from a low-dimensional hierarchical latent space through parametric mappings. Inspired by principal component analysis (PCA), the generative processes for priors, means and covariance matrices are modeled by their respective latent space and parametric mapping. Then, the dependencies between latent spaces are captured by a hierarchical latent space by a linear or kernelized mapping. The function parameters and hierarchical latent space are learned by minimizing the reconstruction error between ground-truth GMMs and manifold-generated GMMs, measured by Kullback-Leibler Divergence (KLD). Variational approximation is employed to handle the intractable KLD between GMMs and a variational EM algorithm is derived to optimize the objective function. Experiments on synthetic data, flow cytometry analysis, eye-fixation analysis and topic models show that PRIMAL learns a continuous and interpretable manifold of GMM distributions and achieves a minimum reconstruction error. [ABSTRACT FROM AUTHOR]

Most existing random access schemes for machine-type communications (MTC) simply adopt a uniform preamble selection distribution, irrespective of the underlying device activity distributions. Hence, they may yield unsatisfactory access efficiency. In this paper, we model device activities for MTC as multiple Bernoulli random variables following an arbitrary multivariate Bernoulli distribution which can reflect both dependent and independent device activities. Then, we optimize preamble selection and access barring for random access in MTC according to the underlying joint device activity distribution. Specifically, we investigate three cases of the joint device activity distribution, i.e., the cases of perfect, imperfect, and unknown joint device activity distributions, and formulate the average, worst-case average, and sample average throughput maximization problems, respectively. The problems in the three cases are challenging nonconvex problems. In the case of perfect joint device activity distribution, we develop an iterative algorithm and a low-complexity iterative algorithm to obtain stationary points of the original problem and an approximate problem, respectively. In the case of imperfect joint device activity distribution, we develop an iterative algorithm and a low-complexity iterative algorithm to obtain a Karush-Kuhn-Tucker (KKT) point of an equivalent problem and a stationary point of an approximate problem, respectively. Finally, in the case of unknown joint device activity distribution, we develop an iterative algorithm to obtain a stationary point. The proposed solutions are widely applicable and outperform existing solutions for dependent and independent device activities. [ABSTRACT FROM AUTHOR]

We present new algorithms for $k$ k -means clustering on a data stream with a focus on providing fast responses to clustering queries. Compared to the state-of-the-art, our algorithms provide substantial improvements in the query time for cluster-center queries while retaining the desirable properties of provably small approximation error and low space usage. Our proposed clustering algorithms systematically reuse the “coresets” (summaries of data) computed for recent queries in answering the current clustering query, a novel technique which we refer to as coreset caching. We also present an algorithm called OnlineCC that integrates the coreset caching idea with a simple sequential streaming $k$ k -means algorithm. In practice, OnlineCC algorithm can provide constant query time. We present both theoretical analysis and detailed experiments demonstrating the correctness, accuracy, and efficiency of all our proposed clustering algorithms. [ABSTRACT FROM AUTHOR]