Wyniki wyszukiwania - Biblioteka Nauki

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Equality in Wielandt’s eigenvalue inequality

100%

Friedland S.

tom 3

nr 1

In this paper we give necessary and sufficient conditions for the equality case in Wielandt’s eigenvalue inequality.

Some approximation problems in semi-algebraic geometry

63%

Friedland S. , Stawiska M.

nr 1

133-147

In this paper we deal with a best approximation of a vector with respect to a closed semi-algebraic set C in the space ℝⁿ endowed with a semi-algebraic norm ν. Under additional assumptions on ν we prove semi-algebraicity of the set of points of unique approximation and other sets associated with the distance to C. For C irreducible algebraic we study the critical point correspondence and introduce the ν-distance degree, generalizing the notion developed by other authors for the Euclidean norm. We discuss separately the case of the $ℓ^p$ norm (p > 1).

A simple spectral algorithm for recovering planted partitions

51%

Cole S. , Friedland S. , Reyzin L.

nr 1

139-157

In this paper, we consider the planted partition model, in which n = ks vertices of a random graph are partitioned into k “clusters,” each of size s. Edges between vertices in the same cluster and different clusters are included with constant probability p and q, respectively (where 0 ≤ q < p ≤ 1). We give an efficient algorithm that, with high probability, recovers the clusters as long as the cluster sizes are are least (√n). Informally, our algorithm constructs the projection operator onto the dominant k-dimensional eigenspace of the graph’s adjacency matrix and uses it to recover one cluster at a time. To our knowledge, our algorithm is the first purely spectral algorithm which runs in polynomial time and works even when s = Θ (√n), though there have been several non-spectral algorithms which accomplish this. Our algorithm is also among the simplest of these spectral algorithms, and its proof of correctness illustrates the usefulness of the Cauchy integral formula in this domain.