Some modifications of the limited-memory variable metric optimization methods
Vlček, Jan; Lukšan, Ladislav
2023 - English
Several modifications of the limited-memory variable metric (or quasi-Newton) line search methods for large scale unconstrained optimization are investigated. First the block version of the symmetric rank-one (SR1) update formula is derived in a similar way as for the block BFGS update in Vlˇcek and Lukˇsan (Numerical Algorithms 2019). The block SR1 formula is then modified to obtain an update which can reduce the required number of arithmetic operations per iteration. Since it usually violates the corresponding secant conditions, this update is combined with the shifting investigated in Vlˇcek and Lukˇsan (J. Comput. Appl. Math. 2006). Moreover, a new efficient way how to realize the limited-memory shifted BFGS method is proposed. For a class of methods based on the generalized shifted economy BFGS update, global convergence is established. A numerical comparison with the standard L-BFGS and BNS methods is given.
Keywords:
unconstrained minimization; variable metric methods; limited-memory methods; variationally derived methods; arithmetic operations reduction; global convergence
Available in a digital repository NRGL
Some modifications of the limited-memory variable metric optimization methods
Several modifications of the limited-memory variable metric (or quasi-Newton) line search methods for large scale unconstrained optimization are investigated. First the block version of the symmetric ...
Spatio-Spectral EEG Patterns in the Source-Reconstructed Space and Relation to Resting-State Networks: An EEG-fMRI Study
Jiříček, Stanislav; Koudelka, V.; Mantini, D.; Mareček, R.; Hlinka, Jaroslav
2022 - English
In this work, we present and evaluate a novel EEG-fMRI integration approach combining a spatio-spectral decomposition method and a reliable source localization technique. On the large 72 subjects resting- state hdEEG-fMRI data set we tested the stability of the proposed method in terms of both extracted spatio-spectral patterns(SSPs) as well as their correspondence to the BOLD signal. We also compared the proposed method with the spatio-spectral decomposition in the electrode space as well as well-known occipital alpha correlate in terms of the explained variance of BOLD signal. We showed that the proposed method is stable in terms of extracted patterns and where they correlate with the BOLD signal. Furthermore, we show that the proposed method explains a very similar level of the BOLD signal with the other methods and that the BOLD signal in areas of typical BOLD functional networks is explained significantly more than by a chance. Nevertheless, we didn’t observe a significant relation between our source-space SSPs and the BOLD ICs when spatio-temporally comparing them. Finally, we report several the most stable source space EEG-fMRI patterns together with their interpretation and comparison to the electrode space patterns.
Keywords:
EEG-fMRI Integration; EEG-informed fMRI; Spatio-spectral Decomposition; Electrical Source Imaging; Independent Component Analysis; Resting State Networks
Available in digital repository of the ASCR
Spatio-Spectral EEG Patterns in the Source-Reconstructed Space and Relation to Resting-State Networks: An EEG-fMRI Study
In this work, we present and evaluate a novel EEG-fMRI integration approach combining a spatio-spectral decomposition method and a reliable source localization technique. On the large 72 subjects ...
Large Perimeter Objects Surrounded by a 1.5D Terrain
Keikha, Vahideh
2022 - English
Given is a 1.5D terrain T , i.e., an x-monotone polygonal chain in R2. Our objective is to approximate the largest area or perimeter convex polygon with at most k vertices inside T . For a constant k > 0, we design an FPTAS that efficiently approximates such polygons within a factor (1 − ǫ). For the special case of the´largest-perimeter contained triangle in T , we design an O(n log n) time exact algorithm that matches the same result for the area measure.
Available in digital repository of the ASCR
Large Perimeter Objects Surrounded by a 1.5D Terrain
Given is a 1.5D terrain T , i.e., an x-monotone polygonal chain in R2. Our objective is to approximate the largest area or perimeter convex polygon with at most k vertices inside T . For a constant k ...
Nearly All Reals Can Be Sorted with Linear Time Complexity
Jiřina, Marcel
2021 - English
We propose a variant of the counting sort modified for sorting reals in a linear time. It is assumed that the sorting key and pointers to the items being sorted are moved and individual items remain at the same place in the memory (in place sorting). In this case, the space complexity of the new variant of the algorithm is the same as the complexity of the quicksort. We also quantify the practical limits for possible sorting reals in a linear time. This possibility is assured under additional assumptions on the distribution of the sorting key, mainly the independence and identity of the distribution. Here we give a more general criteria easily applicable in practice. We also show that the algorithm is applicable for data that do not fulfill criteria for linear time complexity but even that the computation is faster than the system quicksort. A new, faster version of the algorithm is attached.
Keywords:
sorting; algorithm; real sorting key; time complexity; linear complexity
Available in digital repository of the ASCR
Nearly All Reals Can Be Sorted with Linear Time Complexity
We propose a variant of the counting sort modified for sorting reals in a linear time. It is assumed that the sorting key and pointers to the items being sorted are moved and individual items remain ...
Two limited-memory optimization methods with minimum violation of the previous quasi-Newton equations
Vlček, Jan; Lukšan, Ladislav
2020 - English
Limited-memory variable metric methods based on the well-known BFGS update are widely used for large scale optimization. The block version of the BFGS update, derived by Schnabel (1983), Hu and Storey (1991) and Vlček and Lukšan (2019), satisfies the quasi-Newton equations with all used difference vectors and for quadratic objective functions gives the best improvement of convergence in some sense, but the corresponding direction vectors are not descent directions generally. To guarantee the descent property of direction vectors and simultaneously violate the quasi-Newton equations as little as possible in some sense, two methods based on the block BFGS update are proposed. They can be advantageously combined with methods based on vector corrections for conjugacy (Vlček and Lukšan, 2015). Global convergence of the proposed algorithm is established for convex and sufficiently smooth functions. Numerical experiments demonstrate the efficiency of the new methods.
Keywords:
unconstrained minimization; variable metric methods; limited-memory methods; variationally derived methods; global convergence; numerical results
Available in a digital repository NRGL
Two limited-memory optimization methods with minimum violation of the previous quasi-Newton equations
Limited-memory variable metric methods based on the well-known BFGS update are widely used for large scale optimization. The block version of the BFGS update, derived by Schnabel (1983), Hu and Storey ...
Linear-time Algorithms for Largest Inscribed Quadrilateral
Keikha, Vahideh
2020 - English
Let P be a convex polygon of n vertices. We present a linear-time algorithm for the problem of computing the largest-area inscribed quadrilateral of P. We also design the parallel version of the algorithm with O(log n) time and O(n) work in CREW PRAM model, which is quite work optimal. Our parallel algorithm also computes all the antipodal pairs of a convex polygon with O(log n) time and O(log2n+s) work, where s is the number of antipodal pairs, that we hope is of independent interest. We also discuss several approximation algorithms (both constant factor and approximation scheme) for computing the largest-inscribed k-gons for constant values of k, in both area and perimeter measures.
Keywords:
Maximum-area quadrilateral; extreme area k-gon
Available in a digital repository NRGL
Linear-time Algorithms for Largest Inscribed Quadrilateral
Let P be a convex polygon of n vertices. We present a linear-time algorithm for the problem of computing the largest-area inscribed quadrilateral of P. We also design the parallel version of the ...
The Equation |x| - |Ax| = b
Rohn, Jiří
2020 - English
We formulate conditions on A and b under which the double absolute value equation |x| - |Ax| = b possesses in each orthant a unique solution which, moreover, belongs to the interior of that orthant.
Keywords:
absolute value equation; double absolute value equation; orthantwise solvability; theorem of the alternatives
Available in a digital repository NRGL
The Equation |x| - |Ax| = b
We formulate conditions on A and b under which the double absolute value equation |x| - |Ax| = b possesses in each orthant a unique solution which, moreover, belongs to the interior of that orthant.
A Logical Characteristic of Read-Once Branching Programs
Žák, Stanislav
2019 - English
We present a mathematical model of the intuitive notions such as the knowledge or the information arising at different stages of computations on branching programs (b.p.). The model has two appropriate properties: i) The ”knowledge” arising at a stage of computation in question is derivable from the ”knowledge” arising at the previous stage according to the rules of the model and according to the local arrangement of the b.p. ii) The model confirms the intuitively well-known fact that the knowledge arising at a node of a computation depends not only on it but in some cases also on a ”mystery” information. (I. e. different computations reaching the same node may have different knowledge(s) arisen at it.) We prove that with respect to our model no such information exists in read-once b.p.‘s but on the other hand in b. p.‘s which are not read-once such information must be present. The read-once property forms a frontier. More concretely, we may see the instances of our models as a systems S = (U,D) where U is a universe of knowledge and D are derivation rules. We say that a b.p. P is compatible with a system S iff along each computation in P S derives F (false) or T (true) at the end correctly according to the label of the reached sink. This key notion modifies the classic paradigm which takes the computational complexity with respect to different classes of restricted b.p.‘s (e.g. read-once b.p.‘s, k-b.p.‘s, b.p.‘s computing in limited time etc.). Now, the restriction is defined by a subset of systems and only these programs are taken into account which are compatible with at least one of the chosen systems. Further we understand the sets U of knowledge(s) as a sets of admissible logical formulae. It is clear that more rich sets U‘s imply the large restrictions on b.p.‘s and consequently the smaller complexities of Boolean functions are detected. More rich logical equipment implies stronger computational effectiveness. Another question arises: given a set of Boolean functions (e.g. codes of some graphs) what logical equipment is optimal from the point of complexity?
Keywords:
branching programs; computational complexity; logic
Available in digital repository of the ASCR
A Logical Characteristic of Read-Once Branching Programs
We present a mathematical model of the intuitive notions such as the knowledge or the information arising at different stages of computations on branching programs (b.p.). The model has two ...
Absolute Value Mapping
Rohn, Jiří
2019 - English
We prove a necessary and sufficient condition for an absolute value mapping to be bijective. This result simultaneously gives a characterization of unique solvability of an absolute value equation for each right-hand side.
Keywords:
absolute value mapping; bijectivity; interval matrix; regularity; absolute value equation; unique solvability
Available in a digital repository NRGL
Absolute Value Mapping
We prove a necessary and sufficient condition for an absolute value mapping to be bijective. This result simultaneously gives a characterization of unique solvability of an absolute value equation for ...
Overdetermined Absolute Value Equations
Rohn, Jiří
2019 - English
We consider existence, uniqueness and computation of a solution of an absolute value equation in the overdetermined case.
Keywords:
absolute value equations; overdetermined system
Available in a digital repository NRGL
Overdetermined Absolute Value Equations
We consider existence, uniqueness and computation of a solution of an absolute value equation in the overdetermined case.
NRGL provides central access to information on grey literature produced in the Czech Republic in the fields of science, research and education. You can find more information about grey literature and NRGL at service web
Send your suggestions and comments to nusl@techlib.cz
Provider
Other bases