Abstract Kernelized Gram matrix $W$ constructed from data points $\{x_i\}_{i=1}^N$ as $W_{ij}= k_0( \frac{ \| x_i - x_j \|^2} {\sigma ^2} ) $ is widely used in graph-based geometric data analysis and unsupervised learning. An important question is how to choose the kernel bandwidth $\sigma $, and a common practice called self-tuned kernel adaptively sets a $\sigma _i$ at each point $x_i$ by the $k$-nearest neighbor (kNN) distance. When $x_i$s are sampled from a $d$-dimensional manifold embedded in a possibly high-dimensional space, unlike with fixed-bandwidth kernels, theoretical results of graph Laplacian convergence with self-tuned kernels have been incomplete. This paper proves the convergence of graph Laplacian operator $L_N$ to manifold (weighted-)Laplacian for a new family of kNN self-tuned kernels $W^{(\alpha )}_{ij} = k_0( \frac{ \| x_i - x_j \|^2}{ \epsilon \hat{\rho }(x_i) \hat{\rho }(x_j)})/\hat{\rho }(x_i)^\alpha \hat{\rho }(x_j)^\alpha $, where $\hat{\rho }$ is the estimated bandwidth function by kNN and the limiting operator is also parametrized by $\alpha $. When $\alpha = 1$, the limiting operator is the weighted manifold Laplacian $\varDelta _p$. Specifically, we prove the point-wise convergence of $L_N f $ and convergence of the graph Dirichlet form with rates. Our analysis is based on first establishing a $C^0$ consistency for $\hat{\rho }$ which bounds the relative estimation error $|\hat{\rho } - \bar{\rho }|/\bar{\rho }$ uniformly with high probability, where $\bar{\rho } = p^{-1/d}$ and $p$ is the data density function. Our theoretical results reveal the advantage of the self-tuned kernel over the fixed-bandwidth kernel via smaller variance error in low-density regions. In the algorithm, no prior knowledge of $d$ or data density is needed. The theoretical results are supported by numerical experiments on simulated data and hand-written digit image data.
more »
« less
Capacity of Multiple One-Bit Transceivers in a Rayleigh Environment
We analyze the channel capacity of a system with a
large number of one-bit transceivers in a classical Rayleigh environment
with perfect channel information at the receiver. With
M transmitters and N =alpha*M receivers, we derive an expression
of the capacity per transmitter C, where C <= min(1; aalpha), as a
function of alpha and signal-to-noise ratio (SNR) rho, when M -> infinity.
We show that our expression is a good approximation for small
M, and provide simple approximations of C for various ranges
of alpha and rho. We conclude that at high SNR, C reaches its upper
limit of one only if alpha > 1:24. Expressions for determining when
C “saturates” as a function of alpha and rho are given.
more »
« less
- Award ID(s):
- 1731056
- NSF-PAR ID:
- 10061921
- Date Published:
- Journal Name:
- IEEE Wireless Communications and Networking Conference
- ISSN:
- 1525-3511
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Previously, dynamic-assignment Blahut-Arimoto (DAB) was used to find capacity-achieving probability mass functions (PMFs) for binomial channels and molecular channels. As it turns out, DAB can efficiently identify capacity-achieving PMFs for a wide variety of channels. This paper applies DAB to power-constrained (PC) additive white Gaussian Noise (AWGN) Channels and amplitude-constrained (AC) AWGN Channels.This paper modifies DAB to include a power constraint and finds low-cardinality PMFs that approach capacity on PC-AWGN Channels. While a continuous Gaussian PDF is well-known to be capacity-achieving on the PC-AWGN channel, DAB identifies low-cardinality PMFs within 0.01 bits of the mutual information provided by a Gaussian PDF. Recall the results of Ozarow and Wyner requiring a constellation cardinality of ⌈2 ^ (C+1) ⌉ to approach capacity C to within the asymptotic shaping loss of 1.53 dB at high SNR. PMF's found by DAB approach capacity with essentially no shaping loss with cardinality less than 2 ^ (C+1.2) . As expected, DAB's numerical approach identifies PMFs with better mutual information vs. SNR performance than the analytical approaches to finite-support constellations examined by Wu and Verdu. This paper also uses DAB to find capacity-achieving PMFs with small cardinality support sets for AC-AWGN Channels. The resulting evolution of capacity-achieving PMFs as a function of SNR is consistent with the approximate cardinality transition points of Sharma and Shamai.more » « less
-
more » « less
We examine the effects of imperfect phase estimation of a reference signal on the bit error rate and mutual information over a communication channel influenced by fading and thermal noise. The Two-Wave Diffuse-Power (TWDP) model is utilized for statistical characterization of propagation environment where there are two dominant line-of-sight components together with diffuse ones. We derive novel analytical expression of the Fourier series for probability density function arising from the composite received signal phase. Further, the expression for the bit error rate is presented and numerically evaluated. We develop efficient analytical, numerical and simulation methods for estimating the value of the error floor and identifying the range of acceptable signal-to-noise ratio (SNR) values in cases when the floor is present during the detection of multilevel phase-shift keying (PSK) signals. In addition, we use Monte Carlo simulations in order to evaluate the mutual information for modulation orders two, four and eight, and identify its dependence on receiver hardware imperfections under the given channel conditions. Our results expose direct correspondence between bit error rate and mutual information value on one side, and the parameters of TWDP channel, SNR and phase noise standard deviation on the other side. The results illustrate that the error floor values are strongly influenced by the phase noise when signals propagate over a TWDP channel. In addition, the phase noise considerably affects the mutual information.
-
Woodruff, David P. (Ed.)We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the maximum out-degree is bounded. On one hand, we show how to orient the edges such that maximum out-degree is proportional to the arboricity $\alpha$ of the graph, in, either, an amortised update time of $O(\log^2 n \log \alpha)$, or a worst-case update time of $O(\log^3 n \log \alpha)$. On the other hand, motivated by applications including dynamic maximal matching, we obtain a different trade-off. Namely, the improved update time of either $O(\log n \log \alpha)$, amortised, or $O(\log ^2 n \log \alpha)$, worst-case, for the problem of maintaining an edge-orientation with at most $O(\alpha + \log n)$ out-edges per vertex. Finally, all of our algorithms naturally limit the recourse to be polylogarithmic in $n$ and $\alpha$. Our algorithms adapt to the current arboricity of the graph, and yield improvements over previous work: Firstly, we obtain deterministic algorithms for maintaining a $(1+\varepsilon)$ approximation of the maximum subgraph density, $\rho$, of the dynamic graph. Our algorithms have update times of $O(\varepsilon^{-6}\log^3 n \log \rho)$ worst-case, and $O(\varepsilon^{-4}\log^2 n \log \rho)$ amortised, respectively. We may output a subgraph $H$ of the input graph where its density is a $(1+\varepsilon)$ approximation of the maximum subgraph density in time linear in the size of the subgraph. These algorithms have improved update time compared to the $O(\varepsilon^{-6}\log ^4 n)$ algorithm by Sawlani and Wang from STOC 2020. Secondly, we obtain an $O(\varepsilon^{-6}\log^3 n \log \alpha)$ worst-case update time algorithm for maintaining a $(1~+~\varepsilon)\textnormal{OPT} + 2$ approximation of the optimal out-orientation of a graph with adaptive arboricity $\alpha$, improving the $O(\varepsilon^{-6}\alpha^2 \log^3 n)$ algorithm by Christiansen and Rotenberg from ICALP 2022. This yields the first worst-case polylogarithmic dynamic algorithm for decomposing into $O(\alpha)$ forests. Thirdly, we obtain arboricity-adaptive fully-dynamic deterministic algorithms for a variety of problems including maximal matching, $\Delta+1$ colouring, and matrix vector multiplication. All update times are worst-case $O(\alpha+\log^2n \log \alpha)$, where $\alpha$ is the current arboricity of the graph. For the maximal matching problem, the state-of-the-art deterministic algorithms by Kopelowitz, Krauthgamer, Porat, and Solomon from ICALP 2014 runs in time $O(\alpha^2 + \log^2 n)$, and by Neiman and Solomon from STOC 2013 runs in time $O(\sqrt{m})$. We give improved running times whenever the arboricity $\alpha \in \omega( \log n\sqrt{\log\log n})$.more » « less
-
INTRODUCTION Eukaryotes contain a highly conserved signaling pathway that becomes rapidly activated when adenosine triphosphate (ATP) levels decrease, as happens during conditions of nutrient shortage or mitochondrial dysfunction. The adenosine monophosphate (AMP)–activated protein kinase (AMPK) is activated within minutes of energetic stress and phosphorylates a limited number of substrates to biochemically rewire metabolism from an anabolic state to a catabolic state to restore metabolic homeostasis. AMPK also promotes prolonged metabolic adaptation through transcriptional changes, decreasing biosynthetic genes while increasing expression of genes promoting lysosomal and mitochondrial biogenesis. The transcription factor EB (TFEB) is a well-appreciated effector of AMPK-dependent signals, but many of the molecular details of how AMPK controls these processes remain unknown. RATIONALE The requirement of AMPK and its specific downstream targets that control aspects of the transcriptional adaptation of metabolism remain largely undefined. We performed time courses examining gene expression changes after various mitochondrial stresses in wild-type (WT) or AMPK knockout cells. We hypothesized that a previously described interacting protein of AMPK, folliculin-interacting protein 1 (FNIP1), may be involved in how AMPK promotes increases in gene expression after metabolic stress. FNIP1 forms a complex with the protein folliculin (FLCN), together acting as a guanosine triphosphate (GTP)–activating protein (GAP) for RagC. The FNIP1-FLCN complex has emerged as an amino acid sensor to the mechanistic target of rapamycin complex 1 (mTORC1), involved in how amino acids control TFEB activation. We therefore examined whether AMPK may regulate FNIP1 to dominantly control TFEB independently of amino acids. RESULTS AMPK was found to govern expression of a core set of genes after various mitochondrial stresses. Hallmark features of this response were activation of TFEB and increases in the transcription of genes specifying lysosomal and mitochondrial biogenesis. AMPK directly phosphorylated five conserved serine residues in FNIP1, suppressing the function of the FLCN-FNIP1 GAP complex, which resulted in dissociation of RagC and mTOR from the lysosome, promoting nuclear translocation of TFEB even in the presence of amino acids. FNIP1 phosphorylation was required for AMPK to activate TFEB and for subsequent increases in peroxisome proliferation–activated receptor gamma coactivator 1-alpha (PGC1α) and estrogen-related receptor alpha (ERRα) mRNAs. Cells in which the five serines in FNIP1 were mutated to alanine were unable to increase lysosomal and mitochondrial gene expression programs after treatment with mitochondrial poisons or AMPK activators despite the presence and normal regulation of all other substrates of AMPK. By contrast, neither AMPK nor its control of FNIP1 were needed for activation of TFEB after amino acid withdrawal, illustrating the specificity to energy-limited conditions. CONCLUSION Our data establish FNIP1 as the long-sought substrate of AMPK that controls TFEB translocation to the nucleus, defining AMPK phosphorylation of FNIP1 as a singular event required for increased lysosomal and mitochondrial gene expression programs after metabolic stresses. This study also illuminates the larger biological question of how mitochondrial damage triggers a temporal response of repair and replacement of damaged mitochondria: Within early hours, AMPK-FNIP1–activated TFEB induces a wave of lysosome and autophagy genes to promote degradation of damaged mitochondria, and a few hours later, TFEB–up-regulated PGC1⍺ and ERR⍺ promote expression of a second wave of genes specifying mitochondrial biogenesis. These insights open therapeutic avenues for several common diseases associated with mitochondrial dysfunction, ranging from neurodegeneration to type 2 diabetes to cancer. Mitochondrial damage activates AMPK to phosphorylate FNIP1, stimulating TFEB translocation to the nucleus and sequential waves of lysosomal and mitochondrial biogenesis. After mitochondrial damage, activated AMPK phosphorylates FNIP1 (1), causing inhibition of FLCN-FNIP1 GAP activity (2). This leads to accumulation of RagC in its GTP-bound form, causing dissociation of RagC, mTORC1, and TFEB from the lysosome (3). TFEB is therefore not phosphorylated and translocates to the nucleus, inducing transcription of lysosomal or autophagy genes, with parallel increases in NT-PGC1α mRNA (4), which, in concert with ERRα (5), subsequently induces mitochondrial biogenesis (6). CCCP, carbonyl cyanide m-chlorophenylhydrazone; CLEAR, coordinated lysosomal expression and regulation; GDP, guanosine diphosphate; P, phosphorylation. [Figure created using BioRender]more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
