| 1. |
- Andersson, Fredrik K., et al.
(författare)
-
The mathematics of internet search engines
- 2008
-
Ingår i: Acta Applicandae Mathematicae - An International Survey Journal on Applying Mathematics and Mathematical Applications. - : Springer. - 0167-8019 .- 1572-9036. ; 104:2, s. 211-242
-
Tidskriftsartikel (refereegranskat)abstract
- This article presents a survey of techniques for ranking results in search engines, with emphasis on link-based ranking methods and the PageRank algorithm. The problem of selecting, in relation to a user search query, the most relevant documents from an unstructured source such as the WWW is discussed in detail. The need for extending classical information retrieval techniques such as boolean searching and vector space models with link-based ranking methods is demonstrated. The PageRank algorithm is introduced, and its numerical and spectral properties are discussed. The article concludes with an alternative means of computing PageRank, along with some example applications of this new method.
|
|
| 2. |
- Eisenmann, Monika, et al.
(författare)
-
Error estimates of the backward Euler-Maruyama method for multi-valued stochastic differential equations
- 2022
-
Ingår i: Bit Numerical Mathematics. - : Springer Science and Business Media LLC. - 0006-3835 .- 1572-9125. ; 62:3, s. 803-48
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we derive error estimates of the backward Euler-Maruyama method applied to multi-valued stochastic differential equations. An important example of such an equation is a stochastic gradient flow whose associated potential is not continuously differentiable but assumed to be convex. We show that the backward Euler-Maruyama method is well-defined and convergent of order at least 1/4 with respect to the root-mean-square norm. Our error analysis relies on techniques for deterministic problems developed in Nochetto et al. (Commun Pure Appl Math 53(5):525-589, 2000). We verify that our setting applies to an overdamped Langevin equation with a discontinuous gradient and to a spatially semi-discrete approximation of the stochastic p-Laplace equation.
|
|
| 3. |
- Olsson, Carl, 1978, et al.
(författare)
-
Relaxations for Non-Separable Cardinality/Rank Penalties
- 2021
-
Ingår i: Proceedings of the IEEE International Conference on Computer Vision. - 1550-5499. ; 2021-October, s. 162-171
-
Konferensbidrag (refereegranskat)abstract
- Rank and cardinality penalties are hard to handle in optimization frameworks due to non-convexity and discontinuity. Strong approximations have been a subject of intense study and numerous formulations have been proposed. Most of these can be described as separable, meaning that they apply a penalty to each element (or singular value) based on size, without considering the joint distribution. In this paper we present a class of non-separable penalties and give a recipe for computing strong relaxations suitable for optimization. In our analysis of this formulation we first give conditions that ensure that the global ly optimal solution of the relaxation is the same as that of the original (unrelaxed) objective. We then show how a stationary point can be guaranteed to be unique under the restricted isometry property (RIP) assumption.1
|
|
| 4. |
- Limani, Adem, et al.
(författare)
-
On the problem of smooth approximations in H(b) and connections to subnormal operators
- 2023
-
Ingår i: Journal of Functional Analysis. - : Elsevier BV. - 0022-1236 .- 1096-0783. ; 284:5
-
Tidskriftsartikel (refereegranskat)abstract
- For the class of de Branges-Rovnyak spaces H(b) of the unit disk D defined by extreme points b of the unit ball of H infinity, we study the problem of approximation of a general function in H(b) by a function with an extension to the unit circle T of some degree of smoothness, for instance satisfying Holder estimates or being differentiable. We will exhibit connections between this question and the theory of subnormal operators and, in particular, we will tie the possibility of smooth approximations to properties of invariant subspaces of a certain subnormal operator. This leads us to several computable conditions on b which are necessary for such approximations to be possible. For a large class of extreme points b we use our result to obtain explicit necessary and sufficient conditions on the symbol b which guarantee the density of functions with differentiable boundary values in the space H(b). These conditions include an interplay between the modulus of b on T and the spectrum of its inner factor.
|
|
| 5. |
- Olsson, Carl, 1978, et al.
(författare)
-
Non-convex Rank/Sparsity Regularization and Local Minima
- 2017
-
Ingår i: Proceedings of the IEEE International Conference on Computer Vision. - 1550-5499. - 9781538610329 ; 2017-October, s. 332-340
-
Konferensbidrag (refereegranskat)abstract
- This paper considers the problem of recovering either a low rank matrix or a sparse vector from observations of linear combinations of the vector or matrix elements. Recent methods replace the non-convex regularization with ℓ1 or nuclear norm relaxations. It is well known that this approach recovers near optimal solutions if a so called restricted isometry property (RIP) holds. On the other hand it also has a shrinking bias which can degrade the solution. In this paper we study an alternative non-convex regularization term that does not suffer from this bias. Our main theoretical results show that if a RIP holds then the stationary points are often well separated, in the sense that their differences must be of high cardinality/rank. Thus, with a suitable initial solution the approach is unlikely to fall into a bad local minimum. Our numerical tests show that the approach is likely to converge to a better solution than standard ℓ1/nuclear-norm relaxation even when starting from trivial initializations. In many cases our results can also be used to verify global optimality of our method.
|
|
| 6. |
- Danielsson, Joel Larsson, et al.
(författare)
-
Polarised random κ-SAT
- 2023
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 32:6, s. 885-899
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we study a variation of the random κ-SAT problem, called polarised random κ-SAT, which contains both the classical random κ-SAT model and the random version of monotone κ-SAT another well-known NP-complete version of SAT. In this model there is a polarisation parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p = 1/2 we get the classical random κ-SAT model, and at the other extreme we have the fully polarised model where p = 0, or 1. Here there are only two types of clauses: clauses where all κ variables occur pure, and clauses where all κ variables occur negated. That is, for p = 0, and p=1, we get an instance of random monotone κ-SAT. We show that the threshold of satisfiability does not decrease as p moves away from 1/2 and thus that the satisfiability threshold for polarised random κ-SAT with p ≠ 1/2 is an upper bound on the threshold for random κ-SAT. Hence the satisfiability threshold for random monotone κ-SAT is at least as large as for random κ-SAT, and we conjecture that asymptotically, for a fixed κ, the two thresholds coincide.
|
|
| 7. |
- Danielsson, Joel, et al.
(författare)
-
Polarised random k-SAT
- 2022
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- In this paper we study a variation of the random k-SAT problem, called polarized random k-SAT. In this model there is a polarization parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p=1/2 we get the classical random k-SAT model, and at the other extreme we have the fully polarized model where p=0, or 1. Here there are only two types of clauses: clauses where all k variables occur pure, and clauses where all k variables occur negated. That is, for p=0 we get an instance of random monotone k-SAT. We show that the threshold of satisfiability does not decrease as p moves away from 1/2 and thus that the satisfiability threshold for polarized random k-SAT is an upper bound on the threshold for random k-SAT. In fact, we conjecture that asymptotically the two thresholds coincide.
|
|
| 8. |
- Elvander, Filip, et al.
(författare)
-
NON-COHERENT SENSOR FUSION VIA ENTROPY REGULARIZED OPTIMAL MASS TRANSPORT
- 2019
-
Ingår i: 2019 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP). - : IEEE. - 9781479981311 ; , s. 4415-4419
-
Konferensbidrag (refereegranskat)abstract
- This work presents a method for information fusion in source localization applications. The method utilizes the concept of optimal mass transport in order to construct estimates of the spatial spectrum using a convex barycenter formulation. We introduce an entropy regularization term to the convex objective, which allows for low-complexity iterations of the solution algorithm and thus makes the proposed method applicable also to higher-dimensional problems. We illustrate the proposed method's inherent robustness to misalignment and miscalibration of the sensor arrays using numerical examples of localization in two dimensions.
|
|
| 9. |
- Engström, Christian
(författare)
-
Inverse bounds and bulk properties of complex-valued two-component composites
- 2006
-
Ingår i: SIAM Journal on Applied Mathematics. - : Society for Industrial & Applied Mathematics (SIAM). - 0036-1399 .- 1095-712X. ; 67:1, s. 194-213
-
Tidskriftsartikel (refereegranskat)abstract
- The bulk properties of composites are known to depend strongly on the microstructure. This dependence can be quantified in terms of a representation introduced by D. Bergman, which factorizes the geometry dependence from the contrast. Based on this analytic representation of the effective permittivity, we present a general scheme to estimate the microstructural parameters such as the volume fraction and the anisotropy of two-component composites. The estimates are given as bounds, that is, the largest parameter region which is compatible with the available information. Thus, more information produces better estimates on the microstructural parameters. The method, which uses complex-valued measurements of bulk properties of the composite, is illustrated by numerical examples.
|
|
| 10. |
- Federico, Lorenzo, et al.
(författare)
-
Minimal H-factors and covers
- 2023
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- Given a fixed small graph H and a larger graph G, an H-factor is a collection of vertex-disjoint subgraphs H′⊂G, each isomorphic to H, that cover the vertices of G. If G is the complete graph Kn equipped with independent U(0,1) edge weights, what is the lowest total weight of an H-factor? This problem has previously been considered for e.g. H=K2. We show that if H contains a cycle, then the minimum weight is sharply concentrated around some Ln=Θ(n^(1−1/d∗)) (where d∗ is the maximum 1-density of any subgraph of H). Some of our results also hold for H-covers, where the copies of H are not required to be vertex-disjoint.
|
|
