An official website of the United States government
Graphical representations are essential for comprehending high-dimensional data across diverse fields, yet their construction often presents challenges due to the limitations of traditional methods. This paper introduces a novel methodology, Beyond Simplex Sparse Representation (BSSR), which addresses critical issues such as parameter dependencies, scale inconsistencies, and biased data interpretation in constructing similarity graphs. BSSR leverages the robustness of sparse representation to noise and outliers, while incorporating deep learning techniques to enhance scalability and accuracy. Furthermore, we tackle the optimization of the standard simplex, a pervasive problem, by introducing a transformative approach that converts the constraint into a smooth manifold using the Hadamard parametrization. Our proposed Tangent Perturbed Riemannian Gradient Descent (T-PRGD) algorithm provides an efficient and scalable solution for optimization problems with standard simplex or L1-norm sphere constraints. These contributions, including the BSSR methodology, robustness and scalability through deep representation, shift-invariant sparse representation, and optimization on the unit sphere, represent major advancements in the field. Our work offers novel perspectives on data representation challenges and sets the stage for more accurate analysis in the era of big data.
more »
« less
K-Deep Simplex: Manifold Learning via Local Dictionaries
We propose K-Deep Simplex (KDS) which, given a set of data points, learns a dictionary comprising synthetic landmarks, along with representation coefficients supported on a simplex. KDS employs a local weighted l1 penalty that encourages each data point to represent itself as a convex combination of nearby landmarks. We solve the proposed optimization program using alternating minimization and design an efficient, interpretable autoencoder using algorithm unrolling. We theoretically analyze the proposed program by relating the weighted l1 penalty in KDS to a weighted ℓ0 program. Assuming that the data are generated from a Delaunay triangulation, we prove the equivalence of the weighted l1 and weighted l0 programs. We further show the stability of the representation coefficients under mild geometrical assumptions. If the representation coefficients are fixed, we prove that the sub-problem of minimizing over the dictionary yields a unique solution. Further, we show that low-dimensional representations can be efficiently obtained from the covariance of the coefficient matrix. Experiments show that the algorithm is highly efficient and performs competitively on synthetic and real data sets.
more »
« less
- PAR ID:
- 10471333
- Editor(s):
- Duarte, Marco
- Publisher / Repository:
- IEEE
- Date Published:
- Journal Name:
- IEEE Transactions on Signal Processing
- Volume:
- 71
- ISSN:
- 1053-587X
- Page Range / eLocation ID:
- 3741 to 3754
- Subject(s) / Keyword(s):
- optimization sparse coding dictionary learning autoencoders clustering manifold learning
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider the problem of efficiently approximating and encoding high-dimensional data sampled from a probability distribution ρ in ℝD, that is nearly supported on a d-dimensional set - for example supported on a d-dimensional manifold. Geometric Multi-Resolution Analysis (GMRA) provides a robust and computationally efficient procedure to construct low-dimensional geometric approximations of at varying resolutions. We introduce GMRA approximations that adapt to the unknown regularity of , by introducing a thresholding algorithm on the geometric wavelet coefficients. We show that these data-driven, empirical geometric approximations perform well, when the threshold is chosen as a suitable universal function of the number of samples n, on a large class of measures ρ, that are allowed to exhibit different regularity at different scales and locations, thereby efficiently encoding data from more complex measures than those supported on manifolds. These GMRA approximations are associated to a dictionary, together with a fast transform mapping data to d-dimensional coefficients, and an inverse of such a map, all of which are data-driven. The algorithms for both the dictionary construction and the transforms have complexity CDnlogn with the constant C exponential in d. Our work therefore establishes Adaptive GMRA as a fast dictionary learning algorithm, with approximation guarantees, for intrinsically low-dimensional data. We include several numerical experiments on both synthetic and real data, confirming our theoretical results and demonstrating the effectiveness of Adaptive GMRA.more » « less
-
The inverse problem of inferring clinical gold-standard electrocardiogram (ECG) from photoplethysmogram (PPG) that can be measured by affordable wearable Internet of Healthcare Things (IoHT) devices is a research direction receiving growing attention. It combines the easy measurability of PPG and the rich clinical knowledge of ECG for long-term continuous cardiac monitoring. The prior art for reconstruction using a universal basis, such as discrete cosine transform (DCT), has limited fidelity for uncommon ECG shapes due to the lack of representative power. To better utilize the data and improve data representation, we design two dictionary learning frameworks, the cross-domain joint dictionary learning (XDJDL), and the label-consistent XDJDL (LC-XDJDL), to further improve the ECG inference quality and enrich the PPG-based diagnosis knowledge. Building on the K-SVD technique, the proposed joint dictionary learning frameworks extend the expressive power by optimizing simultaneously a pair of signal dictionaries for PPG and ECG with the transforms to relate their sparse codes and disease information. The proposed models are evaluated with a variety of PPG and ECG morphologies from two benchmark datasets that cover various age groups and disease types. The results show the proposed frameworks achieve better inference performance than previous methods with average Pearson coefficients being 0.88 using XDJDL and 0.92 using LC-XDJDL, suggesting an encouraging potential for ECG screening using PPG based on the proactively learned PPG-ECG relationship. By enabling the dynamic monitoring and analysis of the health status of an individual, the proposed frameworks contribute to the emerging digital twins paradigm for personalized healthcare.more » « less
-
null (Ed.)While data filter caches (DFCs) have been shown to be effective at reducing data access energy, they have not been adopted in processors due to the associated performance penalty caused by high DFC miss rates. In this article, we present a design that both decreases the DFC miss rate and completely eliminates the DFC performance penalty even for a level-one data cache (L1 DC) with a single cycle access time. First, we show that a DFC that lazily fills each word in a DFC line from an L1 DC only when the word is referenced is more energy-efficient than eagerly filling the entire DFC line. For a 512B DFC, we are able to eliminate loads of words into the DFC that are never referenced before being evicted, which occurred for about 75% of the words in 32B lines. Second, we demonstrate that a lazily word filled DFC line can effectively share and pack data words from multiple L1 DC lines to lower the DFC miss rate. For a 512B DFC, we completely avoid accessing the L1 DC for loads about 23% of the time and avoid a fully associative L1 DC access for loads 50% of the time, where the DFC only requires about 2.5% of the size of the L1 DC. Finally, we present a method that completely eliminates the DFC performance penalty by speculatively performing DFC tag checks early and only accessing DFC data when a hit is guaranteed. For a 512B DFC, we improve data access energy usage for the DTLB and L1 DC by 33% with no performance degradation.more » « less
-
Kaeli, David (Ed.)While data filter caches (DFCs) have been shown to be effective at reducing data access energy, they have not been adopted in processors due to the associated performance penalty caused by high DFC miss rates. In this article, we present a design that both decreases the DFC miss rate and completely eliminates the DFC performance penalty even for a level-one data cache (L1 DC) with a single cycle access time. First, we show that a DFC that lazily fills each word in a DFC line from an L1 DC only when the word is referenced is more energy-efficient than eagerly filling the entire DFC line. For a 512B DFC, we are able to eliminate loads of words into the DFC that are never referenced before being evicted, which occurred for about 75% of the words in 32B lines. Second, we demonstrate that a lazily word filled DFC line can effectively share and pack data words from multiple L1 DC lines to lower the DFC miss rate. For a 512B DFC, we completely avoid accessing the L1 DC for loads about 23% of the time and avoid a fully associative L1 DC access for loads 50% of the time, where the DFC only requires about 2.5% of the size of the L1 DC. Finally, we present a method that completely eliminates the DFC performance penalty by speculatively performing DFC tag checks early and only accessing DFC data when a hit is guaranteed. For a 512B DFC, we improve data access energy usage for the DTLB and L1 DC by 33% with no performance degradation.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1109/TSP.2023.3322820
