Source author record

Qin Huang

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

ResearcherUnclaimed source record

Information Theory math.IT Data Structures and Algorithms Computational Complexity eess.SP Computational Geometry Computer Vision math.DG physics.med-ph

Catalog footprint

What is connected

13works

9topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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

Building this map preview

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

preprint2023arXiv

A Fundamental Tradeoff Among Storage, Computation, and Communication for Distributed Computing over Star Network

Coded distributed computing can alleviate the communication load by leveraging the redundant storage and computation resources with coding techniques in distributed computing. In this paper, we study a MapReduce-type distributed computing framework over star topological network, where all the workers exchange information through a common access point. The optimal tradeoff among the normalized number of the stored files (storage load), computed intermediate values (computation load) and transmitted bits in the uplink and downlink (communication loads) are characterized. A coded computing scheme is proposed to achieve the Pareto-optimal tradeoff surface, in which the access point only needs to perform simple chain coding between the signals it receives, and information-theretical bound matching the surface is also provided.

preprint2023arXiv

Joint Hybrid Beamforming and User Scheduling for Multi-Satellite Cooperative Networks

In this paper, we consider a cooperative communication network where multiple satellites provide services for ground users (GUs) (at the same time and on the same frequency). The communication and computational resources on satellites are usually restricted and the satellite-GU link determination affects the communication performance significantly when multiple satellites provide services for multiple GUs in a collaborative manner. Therefore, considering the limitation of the on-board radio-frequency chains, we first propose a hybrid beamforming method consisting of analog beamforming for beam alignment and digital beamforming for interference mitigation. Then, to establish appropriate connections between satellites and GUs, we propose a heuristic user scheduling algorithm which determines the connections according to the total spectral efficiency (SE) increment of the multi-satellite cooperative network. Next, a joint hybrid beamforming and user scheduling scheme is proposed to dramatically improve the performance of the multi-satellite cooperative network. Moreover, simulations are conducted to compare the proposed schemes with representative baselines and analyze the key factors influencing the performance of the multi-satellite cooperative network. It is shown that the proposed joint beamforming and user scheduling approach can provide 47.2% SE improvement on average as compared with its non-joint counterpart.

preprint2022arXiv

An AFDM-Based Integrated Sensing and Communications

This paper considers an affine frequency division multiplexing (AFDM)-based integrated sensing and communications (ISAC) system, where the AFDM waveform is used to simultaneously carry communications information and sense targets. To realize AFDM-based sensing functionality, two parameter estimation methods are designed to process echoes in the time domain and the discrete affine Fourier transform (DAFT) domain, respectively. It allows us to decouple delay and Doppler shift in the fast time axis and can maintain good sensing performance even in large Doppler shift scenarios. Numerical results verify the effectiveness of our proposed AFDM-based system in high mobility scenarios.

preprint2021arXiv

Near-Optimal Algorithms for Point-Line Covering Problems

We study fundamental point-line covering problems in computational geometry, in which the input is a set $S$ of points in the plane. The first is the Rich Lines problem, which asks for the set of all lines that each covers at least $λ$ points from $S$, for a given integer parameter $λ\geq 2$; this problem subsumes the 3-Points-on-Line problem and the Exact Fitting problem, which -- the latter -- asks for a line containing the maximum number of points. The second is the NP-hard problem Line Cover, which asks for a set of $k$ lines that cover the points of $S$, for a given parameter $k \in \mathbb{N}$. Both problems have been extensively studied. In particular, the Rich Lines problem is a fundamental problem whose solution serves as a building block for several algorithms in computational geometry. For Rich Lines and Exact Fitting, we present a randomized Monte Carlo algorithm that achieves a lower running time than that of Guibas et al.'s algorithm [Computational Geometry 1996], for a wide range of the parameter $λ$. We derive lower-bound results showing that, for $λ=Ω(\sqrt{n \log n})$, the upper bound on the running time of this randomized algorithm matches the lower bound that we derive on the time complexity of Rich Lines in the algebraic computation trees model. For Line Cover, we present two kernelization algorithms: a randomized Monte Carlo algorithm and a deterministic algorithm. Both algorithms improve the running time of existing kernelization algorithms for Line Cover. We derive lower-bound results showing that the running time of the randomized algorithm we present comes close to the lower bound we derive on the time complexity of kernelization algorithms for Line Cover in the algebraic computation trees model.

preprint2021arXiv

Optimal Streaming Algorithms for Graph Matching

We present parameterized streaming algorithms for the graph matching problem in both the dynamic and the insert-only models. For the dynamic streaming model, we present a one-pass algorithm that, with high probability, computes a maximum-weight $k$-matching of a weighted graph in $\tilde{O}(Wk^2)$ space and that has $\tilde{O}(1)$ update time, where $W$ is the number of distinct edge weights and the notation $\tilde{O}()$ hides a poly-logarithmic factor in the input size. For the insert-only streaming model, we present a one-pass algorithm that runs in $O(k^2)$ space and has $O(1)$ update time, and that, with high probability, computes a maximum-weight $k$-matching of a weighted graph. The space complexity and the update-time complexity achieved by our algorithms for unweighted $k$-matching in the dynamic model and for weighted $k$-matching in the insert-only model are optimal. A notable contribution of this paper is that the presented algorithms {\it do not} rely on the apriori knowledge/promise that the cardinality of \emph{every} maximum-weight matching of the input graph is upper bounded by the parameter $k$. This promise has been a critical condition in previous works, and lifting it required the development of new tools and techniques.

preprint2020arXiv

Linear-Time Parameterized Algorithms with Limited Local Resources

We propose a new (theoretical) computational model for the study of massive data processing with limited computational resources. Our model measures the complexity of reading the very large data sets in terms of the data size N and analyzes the computational cost in terms of a parameter k that characterizes the computational power provided by limited local computing resources. We develop new algorithmic techniques that implement algorithms for solving well-known computational problems on the proposed model. In particular, we present an algorithm that finds a k-matching in a general unweighted graph in time O(N + k^{2.5}) and an algorithm that constructs a maximum weighted k-matching in a general weighted graph in time O(N + k^3 log k). Both algorithms have their space complexity bounded by O(k^2).

preprint2020arXiv

Tethered capsule en face optical coherence tomography for imaging Barrett's esophagus in unsedated patients

Detection of Barrett's esophagus (BE) at points of care outside the endoscopy suite may improve screening access and reduce esophageal adenocarcinoma mortality. Tethered capsule optical coherence tomography (OCT) can volumetrically image esophageal mucosa and detect BE in unsedated patients. We investigated ultrahigh-speed tethered capsule, swept-source OCT (SS-OCT) in unsedated patients, improved device design, developed procedural techniques, measured how capsule contact and longitudinal pullback non-uniformity affect coverage, and assessed patient toleration. OCT was performed in 16 patients prior to endoscopic surveillance/treatment. Unsedated patients swallowed the capsule with small sips of water and the esophagus imaged by retracting the tether. Ultrahigh-speed SS-OCT at 1,000,000 A-scans/second imaged ~40cm$^2$ esophageal areas in 10 seconds with 30um transverse and 8um axial resolution. Nine patients had non-dysplastic BE, 3 had ablative treatment-naive neoplasia, and 4 had prior ablation for history of dysplasia. The capsule procedure was well tolerated. Ultrahigh-speed SS-OCT enabled the generation of cross-sectional and sub-surface en face images. BE could be rapidly identified in cross-sectional and en face images, while assessment of the gastro-esophageal junction (GEJ) required subsurface en face views. Capsule esophageal contact was worse in long-segment BE and sliding hiatal hernia, and longitudinal image coverage was worse in short-segment BE. OCT candidate features of dysplasia are reported. Ultrahigh-speed tethered capsule SS-OCT enabled en face and cross-sectional imaging of mucosal features over wide areas. Device and procedure optimization led to improved imaging performance. Areas of BE could be readily identified, but limited capsule contact and longitudinal image coverage can yield sampling errors.

preprint2016arXiv

Object Boundary Guided Semantic Segmentation

Semantic segmentation is critical to image content understanding and object localization. Recent development in fully-convolutional neural network (FCN) has enabled accurate pixel-level labeling. One issue in previous works is that the FCN based method does not exploit the object boundary information to delineate segmentation details since the object boundary label is ignored in the network training. To tackle this problem, we introduce a double branch fully convolutional neural network, which separates the learning of the desirable semantic class labeling with mask-level object proposals guided by relabeled boundaries. This network, called object boundary guided FCN (OBG-FCN), is able to integrate the distinct properties of object shape and class features elegantly in a fully convolutional way with a designed masking architecture. We conduct experiments on the PASCAL VOC segmentation benchmark, and show that the end-to-end trainable OBG-FCN system offers great improvement in optimizing the target semantic segmentation quality.

preprint2014arXiv

How to select the largest k elements from evolving data?

In this paper we investigate the top-$k$-selection problem, i.e. determine the largest, second largest, ..., and the $k$-th largest elements, in the dynamic data model. In this model the order of elements evolves dynamically over time. In each time step the algorithm can only probe the changes of data by comparing a pair of elements. Previously only two special cases were studied[2]: finding the largest element and the median; and sorting all elements. This paper systematically deals with $k\in [n]$ and solves the problem almost completely. Specifically, we identify a critical point $k^*$ such that the top-$k$-selection problem can be solved error-free with probability $1-o(1)$ if and only if $k=o(k^*)$. A lower bound of the error when $k=Ω(k^*)$ is also determined, which actually is tight under some condition. On the other hand, it is shown that the top-$k$-set problem, which means finding the largest $k$ elements without sorting them, can be solved error-free for all $k\in [n]$. Additionally, we extend the dynamic data model and show that most of these results still hold.

preprint2013arXiv

A Low-Complexity Encoding of Quasi-Cyclic Codes Based on Galois Fourier Transform

The encoding complexity of a general (en,ek) quasi-cyclic code is O[(e^2)(n-k)k]. This paper presents a novel low-complexity encoding algorithm for quasi-cyclic (QC) codes based on matrix transformation. First, a message vector is encoded into a transformed codeword in the transform domain. Then, the transmitted codeword is obtained from the transformed codeword by the inverse Galois Fourier transform. For binary QC codes, a simple and fast mapping is required to post-process the transformed codeword such that the transmitted codeword is binary as well. The complexity of our proposed encoding algorithm is O[e(n-k)k] symbol operations for non-binary codes and O[ek(n-k)(log_2 e)] bit operations for binary codes. These complexities are much lower than their traditional counterpart O[(e^2)(n-k)k]. For example, our complexity of encoding a 64-ary (4095,2160) QC code is only 1.59% of that of traditional encoding, and our complexities of encoding the binary (4095, 2160) and (8176, 7154) QC codes are respectively 9.52% and 1.77% of those of traditional encoding. We also study the application of our low-complexity encoding algorithm to one of the most important subclasses of QC codes, namely QC-LDPC codes, especially when their parity-check matrices are rank deficient.

preprint2013arXiv

Applications of Some Elliptic Equations in Riemannian Manifolds

Let $(M^{n+1}, g)$ be a compact Riemannian manifold with smooth boundary B and nonnegative Bakry-Emery Ricci curvature. In this paper, we use the solvability of some elliptic equations to prove some estimates of the weighted mean curvature and some related rigidity theorems. As their applications, we obtain some lower bound estimate of the first nonzero eigenvalue of the drifting Laplacian acting on functions on B and some corresponding rigidity theorems.

preprint2012arXiv

Low-Density Arrays of Circulant Matrices: Rank and Row-Redundancy Analysis, and Quasi-Cyclic LDPC Codes

This paper is concerned with general analysis on the rank and row-redundancy of an array of circulants whose null space defines a QC-LDPC code. Based on the Fourier transform and the properties of conjugacy classes and Hadamard products of matrices, we derive tight upper bounds on rank and row-redundancy for general array of circulants, which make it possible to consider row-redundancy in constructions of QC-LDPC codes to achieve better performance. We further investigate the rank of two types of construction of QC-LDPC codes: constructions based on Vandermonde Matrices and Latin Squares and give combinatorial expression of the exact rank in some specific cases, which demonstrates the tightness of the bound we derive. Moreover, several types of new construction of QC-LDPC codes with large row-redundancy are presented and analyzed.

preprint2010arXiv

Cyclic and Quasi-Cyclic LDPC Codes on Row and Column Constrained Parity-Check Matrices and Their Trapping Sets

This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly LDPC codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterizations of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite geometry LDPC codes using the results developed in first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping sets of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite geometry and finite field cyclic and quasi-cyclic LDPC codes with large minimum weights are shown to have no harmful trapping sets with size smaller than their minimum weights. Consequently, their performance error-floors are dominated by their minimum weights.