More Like this

1. Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design

   https://doi.org/doi:10.1137/1.9781611975482.84  

   Nikolov, A ; Singh, M. ; Tantipongpipat, U. ( January 2019 , Symposium on Discrete Algorithms (SODA))

   We study the A-optimal design problem where we are given vectors υ1, …, υn ∊ ℝd, an integer k ≥ d, and the goal is to select a set S of k vectors that minimizes the trace of (∑i∊Svivi⊺)−1. Traditionally, the problem is an instance of optimal design of experiments in statistics [35] where each vector corresponds to a linear measurement of an unknown vector and the goal is to pick k of them that minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. The problem also finds applications in sensor placement in wireless networks [22], sparse least squares regression [8], feature selection for k-means clustering [9], and matrix approximation [13, 14, 5]. In this paper, we introduce proportional volume sampling to obtain improved approximation algorithms for A-optimal design. Given a matrix, proportional volume sampling involves picking a set of columns S of size k with probability proportional to µ(S) times det(∑i∊Svivi⊺) for some measure µ. Our main result is to show the approximability of the A-optimal design problem can be reduced to approximate independence properties of the measure µ. We appeal to hardcore distributions as candidate distributions µ that allow us to obtain improved approximation algorithms for the A-optimal design. Our results include a d-approximation when k = d, an (1 + ∊)-approximation when and -approximation when repetitions of vectors are allowed in the solution. We also consider generalization of the problem for k ≤ d and obtain a k-approximation. We also show that the proportional volume sampling algorithm gives approximation algorithms for other optimal design objectives (such as D-optimal design [36] and generalized ratio objective [27]) matching or improving previous best known results. Interestingly, we show that a similar guarantee cannot be obtained for the E-optimal design problem. We also show that the A-optimal design problem is NP-hard to approximate within a fixed constant when k = d. 

   more » « less
2. Distributed Constraint Optimization Problem for Coordinated Response of Unmanned Aerial Vehicles and Ground Vehicles

   https://doi.org/10.1109/CISS50987.2021.9400249  

   Darko, Justice ; Folsom, Larkin ; Deshpande, Niharika ; Park, Hyoshin ( March 2021 , The 55th Annual Conference on Information Sciences and Systems)

   While there has been significant progress on statistical theories in the information community, there is a lack of studies in information-theoretic distributed resource allocation to maximize information gain. With advanced technologies of unmanned aerial vehicles (UAVs) in response to corresponding revised FAA regulations, this study focuses on developing a new framework for utilizing UAVs in incident management. As a result of new computing technologies, predictive decision-making studies have recently improved ERV allocations for a sequence of incidents; however, these ground-based operations do not simultaneously capture network-wide information. This study incorporates a real-time aerial view using UAVs with three key improvements. First, aerial observations update the status of the freeway shoulder, allowing an ERV to safely travel at full speed. Second, observing parameters of the congestion shockwave provides accurate measurements of the true impact of an incident. Third, real-time information can be gathered on the clearance progress of an incident scene. We automate UAV and ERV allocation while satisfying constraints between these vehicles using a distributed constraint optimization problem (DCOP) framework. To find the optimal assignment of vehicles, the proposed model is formulated and solved using the Max-Sum approach. The system utility convergence is presented for different scenarios of grid size, number of incidents, and number of vehicles. We also present the solution of our model using the Distributed Stochastic Algorithm (DSA). DSA with exploration heuristics outperformed the Max-Sum algorithm when probability threshold p=0.5 but degrades for higher values of p. 

   more » « less
3. Fast Optimal Circular Clustering and Applications on Round Genomes

   https://doi.org/10.1109/TCBB.2021.3077573  

   Debnath, Tathagata ; Song, Mingzhou ( June 2021 , IEEE/ACM Transactions on Computational Biology and Bioinformatics)

   null (Ed.)

   Round genomes are found in bacteria, plant chloroplasts, and mitochondria. Genetic or epigenetic marks can present biologically interesting clusters along a circular genome. The circular data clustering problem groups N points on a circle into K clusters to minimize the within-cluster sum of squared distances. Repeatedly applying the K-means algorithm takes quadratic time, impractical for large circular datasets. To overcome this issue, we developed a fast, reproducible, and optimal circular clustering (FOCC) algorithm of worst-case O(KN log^2 N) time. The core is a fast optimal framed clustering algorithm, which we designed by integrating two divide-and-conquer and one bracket dynamic programming strategies. The algorithm is optimal based on a property of monotonic increasing cluster borders over frames on linearized data. On clustering 50,000 circular data points, FOCC outruns brute-force or heuristic circular clustering by three orders of magnitude. We produced clusters of CpG sites and genes along three round genomes, exhibiting higher quality than heuristic clustering. More broadly, the presented subquadratic-time algorithms offer the fastest known solution to not only framed and circular clustering, but also angular, periodical, and looped clustering. We implemented these algorithms in the R package OptCirClust (https://CRAN.R-project.org/package=OptCirClust) 

   more » « less
4. Ensuring reliable connectivity to cellular-connected UAVs with up-tilted antennas and interference coordination

   https://doi.org/10.52953/LEFT7402  

   Uddin, Md Moin ; Guvenc, Ismail ; Saad, Walid ; Bhuyan, Arupjyoti ( January 2021 , ITU Journal on Future and Evolving Technologies)

   To integrate unmanned aerial vehicles (UAVs) in future large-scale deployments, a new wireless communication paradigm, namely, the cellular-connected UAV has recently attracted interest. However, the line-of-sight dominant air-to-ground channels along with the antenna pattern of the cellular ground base stations (GBSs) introduce critical interference issues in cellular-connected UAV communications. In particular, the complex antenna pattern and the ground reflection (GR) from the down-tilted antennas create both coverage holes and patchy coverage for the UAVs in the sky, which leads to unreliable connectivity from the underlying cellular network. To overcome these challenges, in this paper, we propose a new cellular architecture that employs an extra set of co-channel antennas oriented towards the sky to support UAVs on top of the existing down-tilted antennas for ground user equipment (GUE). To model the GR stemming from the down-tilted antennas, we propose a path-loss model, which takes both antenna radiation pattern and configuration into account. Next, we formulate an optimization problem to maximize the minimum signal-to-interference ratio (SIR) of the UAVs by tuning the up-tilt (UT) angles of the up-tilted antennas. Since this is an NP-hard problem, we propose a genetic algorithm (GA) based heuristic method to optimize the UT angles of these antennas. After obtaining the optimal UT angles, we integrate the 3GPP Release-10 specified enhanced inter-cell interference coordination (eICIC) to reduce the interference stemming from the down-tilted antennas. Our simulation results based on the hexagonal cell layout show that the proposed interference mitigation method can ensure higher minimum SIRs for the UAVs over baseline methods while creating minimal impact on the SIR of GUEs. 

   more » « less
5. Toeplitz Inverse Covariance Based Robust Speaker Clustering for Naturalistic Audio Streams

   https://doi.org/10.21437/Interspeech.2019-1102  

   Dubey, Harishchandra ; Sangwan, Abhijeet ; Hansen, John H.L. ( September 2019 , ISCA INTERSPEECH-2019)

   Speaker diarization determines who spoke and when? in an audio stream. In this study, we propose a model-based approach for robust speaker clustering using i-vectors. The i-vectors extracted from different segments of same speaker are correlated. We model this correlation with a Markov Random Field (MRF) network. Leveraging the advancements in MRF modeling, we used Toeplitz Inverse Covariance (TIC) matrix to represent the MRF correlation network for each speaker. This approaches captures the sequential structure of i-vectors (or equivalent speaker turns) belonging to same speaker in an audio stream. A variant of standard Expectation Maximization (EM) algorithm is adopted for deriving closed-form solution using dynamic programming (DP) and the alternating direction method of multiplier (ADMM). Our diarization system has four steps: (1) ground-truth segmentation; (2) i-vector extraction; (3) post-processing (mean subtraction, principal component analysis, and length-normalization) ; and (4) proposed speaker clustering. We employ cosine K-means and movMF speaker clustering as baseline approaches. Our evaluation data is derived from: (i) CRSS-PLTL corpus, and (ii) two meetings subset of the AMI corpus. Relative reduction in diarization error rate (DER) for CRSS-PLTL corpus is 43.22% using the proposed advancements as compared to baseline. For AMI meetings IS1000a and IS1003b, relative DER reduction is 29.37% and 9.21%, respectively. 

   more » « less