In this paper, we introduce an efficient and effective algorithm for Graph-based Semi-Supervised Learning (GSSL). Unlike other GSSL methods, our proposed algorithm achieves efficiency by constructing a bipartite graph, which connects a small number of representative points to a large volume of raw data by capturing their underlying manifold structures. This bipartite graph, with a sparse and anti-diagonal affinity matrix which is symmetrical, serves as a low-rank approximation of the original graph. Consequently, our algorithm accelerates both the graph construction and label propagation steps. In particular, on the one hand, our algorithm computes the label propagation in closed-form, reducing its computational complexity from cubic to approximately linear with respect to the number of data points; on the other hand, our algorithm calculates the soft label matrix for unlabeled data using a closed-form solution, thereby gaining additional acceleration. Comprehensive experiments performed on six real-world datasets demonstrate the efficiency and effectiveness of our algorithm in comparison to five state-of-the-art algorithms.
This paper discusses a reduction in the optimal time due to the presence of input redundancy in time-optimal control problems. By introducing a non-idle channel to represent an active input channel, we establish the necessary and sufficient conditions that ensure a strict reduction in the optimal time for affine nonlinear systems. In cases of identical input redundancy, its impact varies according to the type of input constraint, and certain types may not lead to a reduction in the optimal time. Ultimately, in linear time-invariant (LTI) systems, the extent of the optimal time reduction depends on the system’s controllability.
This paper introduces the Group Forward–Backward Orthogonal Matching Pursuit (Group-FoBa-OMP) algorithm, a novel approach for sparse feature selection. The core innovations of this algorithm include (1) an integrated backward elimination process to correct earlier misidentified groups; (2) a versatile convex smooth model that generalizes previous research; (3) the strategic use of gradient information to expedite the group selection phase; and (4) a theoretical validation of its performance in terms of support set recovery, variable estimation accuracy, and objective function optimization. These advancements are supported by experimental evidence from both synthetic and real-world data, demonstrating the algorithm’s effectiveness.
This paper introduces a novel kind of factorial hidden Markov model (FHMM), specifically the feedforward FHMM (FFHMM). In contrast to traditional FHMMs, the FFHMM is capable of directly utilizing supplementary information from observations through predefined states, which are derived using an automatic feature filter (AFF). We investigate two variations of FFHMM models that integrate predefined states with the FHMM: the direct FFHMM and the embedded FFHMM. In the direct FFHMM, alterations to one sub-hidden Markov model (HMM) do not affect the others, enabling individual improvements in HMM estimation. On the other hand, the sub-HMM chains within the embedded FFHMM are interconnected, suggesting that adjustments to one HMM chain may enhance the estimations of other HMM chains. Consequently, we propose two algorithms for these FFHMM models to estimate their respective hidden states. Ultimately, experiments conducted on two real-world datasets validate the efficacy of the proposed models and algorithms.