text:
# Regression (curve fitting)

## Regression

Regression or fiting methods referred to a series of measurement data to determine the parameters of a given function or best to approach.

## Least Square Fit

The least squares method is to determine the parameters of a curve such that the root mean square deviation is minimized. In statistics, the method of regression analysis will be used.

## Fourier Series

The development of a periodic function into a series of trigonometric functions does the Fourier series. The development of a function in its Fourier series is known as harmonic analysis.

## Mean values and standard deviation

The arithmetic means

$x ‾ = 1 n ∑ i = 1 n x i$

$y ‾ = 1 n ∑ i = 1 n y i$

Standard deviation from the mean

$σ = 1 n-1 ∑ i = 1 n x i - x ‾ 2$

For the standard deviation of the regression line of the average value of x of the relevant function value of the straight line is to be replaced.

## Fit line for power laws

If the measured values is an exponential relationship is based can also be used for the best fit straight line linear model. Therefore it is necessary to take the logarithm, the measured values, because then gives a linear equation by substitution.

$y=b\cdot {a}^{x}$

Logarithm leads to a linear equation.

$\mathrm{ln}y=\mathrm{ln}b+x\mathrm{ln}a$

With the logarithm of measured values y' and the substitutions a' = ln a and b'= ln b is present, the linear model.

$\mathrm{y\text{'}}=\mathrm{b\text{'}}+\mathrm{a\text{'}}x$

## Regression

The regression analysis is used for determining or estimating model parameters. The starting point are measured values and a model that the measured values should be based on. Since the measured values generally subject to fault optimizes the regression analysis, the model parameters to optimal adaptation. The basic procedure is the method of least squares.

## Least square method

The method of least squares, a method of compensation calculation. With the method, an optimum compromise is calculated, in which the squares of the deviations are minimized by the model function.

With respect to the measured values (x i , y i ) and the model function f is the quadratic deviation is minimized. To achieve this, the parameters a i of the model function are determined so that the following condition is satisfied.

$∑ i = 1 n f x i a → - y i 2 → min$

### Model function: Linear fit

For the determination of the regression line is a linear model function f is used for the least squares method.

$f\left(x,\stackrel{\to }{a}\right)={a}_{0}+{a}_{1}x$

The deviation of the regression line to the measured values is then given as follows.

$\begin{array}{c}{a}_{0}+{a}_{1}{x}_{1}-{y}_{1}={r}_{1}\\ {a}_{0}+{a}_{2}{x}_{2}-{y}_{2}={r}_{2}\\ ⋮\\ {a}_{0}+{a}_{n}{x}_{n}-{y}_{n}={r}_{n}\end{array}$

The goal now is the sum of squares of the deviations from a straight line r to make as small as possible.

$\sum _{i=1}^{n}{r}_{i}^{2}$ $={\left({a}_{0}+{a}_{1}{x}_{1}-{y}_{1}\right)}^{2}+\dots$ $+{\left({a}_{0}+{a}_{n}{x}_{n}-{y}_{n}\right)}^{2}$ $\to \text{min}$

The extremum is determined by the partial derivatives with respect to a 0 and a be set 1 zero.

$\frac{\partial }{\partial {a}_{0}}{\left({a}_{0}+{a}_{1}{x}_{1}-{y}_{1}\right)}^{2}+\dots$ $+{\left({a}_{0}+{a}_{n}{x}_{n}-{y}_{n}\right)}^{2}=0$

$\frac{\partial }{\partial {a}_{1}}{\left({a}_{0}+{a}_{1}{x}_{1}-{y}_{1}\right)}^{2}+\dots$ $+{\left({a}_{0}+{a}_{n}{x}_{n}-{y}_{n}\right)}^{2}=0$

The resolution of the equation system provides the parameters a 0 and a 1 of the regression line.

$a0 =y‾-a1x‾$

$a1 = ∑ i = 1 n x i - x ‾ y i - y ‾ ∑ i = 1 n x i - x ‾ 2$

#### Calculator: fit line

Number of measurement points n=

### Model function: power functions

The approximation of a power function is performed by returning to the linear model function.

$y=a\cdot {x}^{b}$

Logarithm leads to a linear equation.

$\mathrm{ln}y=\mathrm{ln}a+b\mathrm{ln}x$

With the logarithmic measurement values y 'and the substitutions a' = ln a and x '= ln x is the linear model before.

$\mathrm{y\text{'}}=\mathrm{a\text{'}}+b\mathrm{x\text{'}}$

#### Calculator: Power function

Number of measurement points n=

### Approximation (fit) der Gauß-Verteilung an Messwerte

Die Gauß-Verteilung auch Normalverteilung genannt ist folgendermaßen definiert:

$f\left(x\right)=\frac{1}{\sqrt{2\pi }\sigma }\phantom{\rule{0.3em}{0ex}}{e}^{-\frac{1}{2}\frac{{\left(x-\mu \right)}^{2}}{{\sigma }^{2}}}$

#### Calculator: Normal distribution

The adaptation (fit) of the Gaussian distribution to the measured values takes place by forming the weighted mean value of the measured values. The weighted mean value corresponds to the μ In the Gaussian distribution. The standard deviation of the measured values from the mean value is the σ in the normal distribution.

$\mu =\frac{\sum _{i=1}^{n}{x}_{i}{y}_{i}}{\sum _{i=1}^{n}{y}_{i}}$

$σ = ∑ i = 1 n x i - μ 2 y i ∑ i = 1 n y i$

Number of measuring points n=

### Model function: Periodically (Fourier series)

Measured values can also be approximated by the periodic functions. The procedure for this is the development of a Fourier series. The elements of the Fourier series are sine and cosine functions. The development takes place in ascending order of frequencies.

The Fourier series is:

$snx= a 0 2 + ∑ k = 1 n a k cos k ω x + b k sin k ω x$

with the Fourier coefficients a k and b k and ω = 2π / T. This is the period T = b - a with the initial interval a and the end of interval b.

The Fourier coefficients a k and b k satisfy the least squares condition for the associated sine or cosine function. The coefficients are calculated as follows.

$ak= 2 l ∫ a b f x cos k ω x dx$

$bk= 2 l ∫ a b f x sin k ω x dx$

#### Calculator: Fourier approximation

Number of measurement points n=

x-min=

x-max=

#### Enter the measured values: x1, y1, x2, y2, ...

Number of Fourier terms k=

#### Fourier coefficients

The Fourier coefficients a k and b k are here computed numerically using the trapezoidal method for the numerical integration. The accuracy can be improved by increasing the number of measurements is increased in the interval.

### Polynomial approximation using the QR method

The linear approximation problem is solved by the QR decomposition. The calculator determines the coefficients of the n-th degree polynomial.

The starting point is the over-determined system of equations:

$Ax=b$

$\text{with}\phantom{\rule{1em}{0ex}}x\phantom{\rule{0.5em}{0ex}}\in \phantom{\rule{0.5em}{0ex}}{\mathbb{R}}^{n}\phantom{\rule{1em}{0ex}}\text{und}\phantom{\rule{1em}{0ex}}A\phantom{\rule{0.5em}{0ex}}\in \phantom{\rule{0.5em}{0ex}}{\mathbb{R}}^{nxm}$

The QR decomposition leads to the factorization of the matrix A:

$A=QR$

This applies to the compensation problem:

${||Ax-b||}_{2}^{2}={||QRx-b||}_{2}^{2}={||{R}^{*}x-{Q}^{\mathrm{T*}}b||}_{2}^{2}$

here R and Q are reduced to the relevant proportion. That is, R * is the upper triangular matrix of R and Q T * contains the corresponding rows of Q.

Replacing A by the Vandermond matrix with the corresponding measured values x i and b by the measured values y i yields the coefficients of the compensating polynomial as the solution of the equation system.

#### Calculator: Polynomial approximation

Number of measuring points n=

Degree of the polynomial =


text:
# Does the accelerated rate of expansion of the Universe have any effect on the speed of light in vacuum?

So I was just wondering about this as I finished reading about Michelson-Morley's experiment which disproved the ether theory. My question is since the Universe is constantly expanding and that too with an accelerated rate does it somehow effect the experimental conditions? If so I wanna know how because I'm unable to understand what effects would expansion of space have on the velocity of light. Is the speed of light not a constant then?

The expansion of the Universe has no effect on the local speed of light. Any local measurement of $c$ will yield $c$, and $c$ won't change.

There is one thing that often causes confusion about the speed of light or faster-than-light travel. A photon moving in an expanding space-time appears to move at an average speed faster than $c$. Consider a simplified/idealized scenario: a photon is directed at a target 2 lightyears away. It travels at $c$ for one year, covering a distance of 1 lightyear. Then the Universe it is travelling in undergoes a near-instantaneous expansion to double its previous size. Now it is 2 light years from its starting point, and 2 lightyears from its target. It keeps travelling at $c$, so it takes 2 more years to reach its target. Now suppose you decided to calculate the average speed of the photon. It is now 4 lightyears from its starting point, and it made the journey in 3 years, so its average speed was $\frac{4}{3}c$. But this is not a local measurement of $c$; I said before that the photon was travelling at $c$ the whole time, and any local measurement at any time would have given $c$. It's just that the space between the origin and target of the photon changed while it travelled. This "sudden" expansion is of course not very realistic and I just chose it to make my point easy to illustrate, but the same concept applies for gradual expansion, demonstrating so just requires a few integrals.

• A photon moving in expanding spacetime should appear to reach its target slower than it would have in non-expanding spacetime don't you think? Cause the distance will be increased. In reference to what you said in sentence 2 para 2. Aug 13, 2015 at 15:40
• Also does this expansion of space imply that our instruments will be expanded too hence giving us the illusion that 'c' is a constant? Is that the case? Also if that is the case then does it mean that atoms have grown in size since the beginning of the universe? Aug 13, 2015 at 15:43
• @eoshah It will take longer for a photon to make a trip if you base your estimate of the travel time on the distance when the trip begins, because of course the distance will get larger during the trip. Aug 13, 2015 at 16:59
• @eoshah As to your second question about the instruments expanding - they do not. On smaller scales other forces can resist the expansion, for instance gravity, electromagnetism, etc. See this question for instance. Aug 13, 2015 at 17:02

The Michelson-Morley experiment indicated (contrarily to it's original intent), that the speed of light perceived by an observer is not dependent on their speed relative to anything.

Along these lines, our movement in space with respect to any arbitrary point has no impact on the speed of light measured in the earth system.

Disclaimer: did not hear a course on general relativity yet.

Does the accelerated rate of expansion of the Universe have any effect on the velocity of light?

This is the subject of some debate. Check out the Wikipedia Variable Speed of Light article:

"The idea from Moffat and the team Albrecht–Magueijo is that light propagated as much as 60 orders of magnitude faster in the early universe, thus distant regions of the expanding universe have had time to interact at the beginning of the universe".

I think this idea is wrong myself. See the Einstein digital papers. Einstein said light curves because the speed of light varies with position. He never said light curves because spacetime is curved, that's a popscience myth. See Baez for more: "In that sense, we could say that the 'ceiling' speed of light in the presence of gravity is higher than the 'floor' speed of light". Applying this to cosmology would mean the speed of light was slower in the early universe, not faster.

I'm afraid that's popscience too. See the Einstein digital papers for Einstein talking about ether in 1920: "Recapitulating, we may say that according to the general theory of relativity space is endowed with physical qualities; in this sense, therefore, there exists an ether". Einstein removed the need for the luminiferous aether in 1905, but he was still saying space is an aether in 1920. Search arXiv for papers with aether in the title.

My question is since the Universe is constantly expanding and that too with an accelerated rate does it somehow effect the experimental conditions? If so I wanna know how because I'm unable to understand what effects would expansion of space have on the velocity of light.

Nobody can give you any definite answers at the moment. In five years maybe the situation will be different.

Is the speed of light not a constant then?

No. The locally-measured speed of light appears to be constant because we use the local motion of light to define our second and our metre, which we then use to measure the local speed of light! It's a tautology. Magueijo and Moffat referred to it in http://arxiv.org/abs/0705.4507:

"Following Ellis, let us first consider c as the speed of the photon. Can c vary? Could such a variation be measured? As correctly pointed out by Ellis, within the current protocol for measuring time and space the answer is no. The unit of time is defined by an oscillating system or the frequency of an atomic transition, and the unit of space is defined in terms of the distance travelled by light in the unit of time. We therefore have a situation akin to saying that the speed of light is 'one light-year per year', i.e. its constancy has become a tautology or a definition."

• You keep going on about those Einstein papers, yet the very same page you cite for Einstein saying the speed of light is variable goes on to clarify with EXACTLY THE POINT OF VIEW YOU DERISIVELY CALL POPSCI. "[...] this very fact shows that in the vicinity of every world point the results of the theory of special relativity are valid (in the infinitesimal) for a suitably chosen local coordinate system." The standard physics is that the SR holds locally ($c$ is constant), and any measurement of $c$ must be local to be valid. Your explanation isn't wrong, but it is confusing and misleading. Aug 7, 2015 at 16:37
• @Kyle Oman : it isn't misleading. What is, is forgetting about in the infinitesimal and claiming that the speed of light is constant everywhere. See Shapiro: "the speed of a light wave depends on the strength of the gravitational potential along its path". It isn't constant in the room you're in, read that Baez article. Your local measurement of c is only constant because of the tautology wherein the local motion of light defines your second and your metre. Aug 8, 2015 at 7:13
• See Baez for more... As noted elsewhere by me, the author of that article is Don Koks, not Baez. It is both intentionally misleading & ethically wrong for you to attribute that quote to Baez. Aug 18, 2015 at 19:09

format: plain


text:
# Scalable Fair Clustering

We study the fair variant of the classic k-median problem introduced by Chierichetti et al. [2017]. In the standard k-median problem, given an input pointset P, the goal is to find k centers C and assign each input point to one of the centers in C such that the average distance of points to their cluster center is minimized. In the fair variant of k-median, the points are colored, and the goal is to minimize the same average distance objective while ensuring that all clusters have an "approximately equal" number of points of each color. Chierichetti et al. proposed a two-phase algorithm for fair k-clustering. In the first step, the pointset is partitioned into subsets called fairlets that satisfy the fairness requirement and approximately preserve the k-median objective. In the second step, fairlets are merged into k clusters by one of the existing k-median algorithms. The running time of this algorithm is dominated by the first step, which takes super-quadratic time. In this paper, we present a practical approximate fairlet decomposition algorithm that runs in nearly linear time. Our algorithm additionally allows for finer control over the balance of resulting clusters than the original work. We complement our theoretical bounds with empirical evaluation.

## Authors

• 12 publications
• 23 publications
• 8 publications
• 7 publications
• 14 publications
• 11 publications
• ### (Individual) Fairness for k-Clustering

We give a local search based algorithm for k-median (k-means) clustering...
02/17/2020 ∙ by Sepideh Mahabadi, et al. ∙ 0

• ### Coresets for Clustering with Fairness Constraints

In a recent work, Chierichetti et al. studied the following "fair" varia...
06/20/2019 ∙ by Lingxiao Huang, et al. ∙ 0

• ### KFC: A Scalable Approximation Algorithm for k-center Fair Clustering

In this paper, we study the problem of fair clustering on the k-center o...
10/26/2020 ∙ by Elfarouk Harb, et al. ∙ 0

• ### Better Algorithms for Individually Fair k-Clustering

We study data clustering problems with ℓ_p-norm objectives (e.g. k-Media...
06/23/2021 ∙ by Deeparnab Chakrabarty, et al. ∙ 0

• ### Hierarchical Recursive Running Median

To date, the histogram-based running median filter of Perreault and Hébe...
05/19/2011 ∙ by Alexander Alekseychuk, et al. ∙ 0

• ### Fair Coresets and Streaming Algorithms for Fair k-Means Clustering

We study fair clustering problems as proposed by Chierichetti et al. Her...
12/28/2018 ∙ by Melanie Schmidt, et al. ∙ 0

• ### On Efficient Low Distortion Ultrametric Embedding

A classic problem in unsupervised learning and data analysis is to find ...

##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

The success of machine learning led to its widespread adoption in many aspects of our daily lives. Automatic prediction and forecasting methods are now used to approve mortgage applications or estimate the likelihood of recidivism. It it thus crucial to design machine learning algorithms that are

fair, i.e., do not suffer from bias against or towards particular population groups. An extensive amount of research over the last few years has focused on two key questions: how to formalize the notion of fairness in the context of common machine learning tasks, and how to design efficient algorithms that conform to those formalizations. See e.g., the survey by Chouldechova and Roth (2018) for an overview.

In this paper we focus on the second aspect. Specifically, we consider the problem of fair clustering and propose efficient algorithms for solving this problem. Fair clustering, introduced in  Chierichetti et al. (2017), generalizes the standard notion of clustering by imposing a constraint that all clusters must be balanced with respect to specific sensitive attributes, such as gender or religion. In the simplest formulation, each input point is augmented with one of two colors (say, red and blue), and the goal is to cluster the data while ensuring that, in each cluster, the fraction of points with the less frequent color is bounded from below by some parameter strictly greater than . Chierichetti et al. (2017) proposed polynomial time approximation algorithms for fair variants of classic clustering methods, such as -center (minimize the maximum distance between points and their cluster centers) and -median (minimize the average distance between points and their cluster centers). To this end, they introduced the notion of fairlet decomposition: a partitioning of the input pointset into small subsets, called fairlets, such that a good balanced clustering can be obtained by merging fairlets into clusters. Unfortunately, their algorithm for computing a fairlet decomposition has running time that is at least quadratic in the number of the input points. As a result, the algorithm is applicable only to relatively small data sets.

In this paper we address this drawback and propose an algorithm for computing fairlet decompositions with running time that is near-linear in the data size. We focus on the -median formulation, as

-center clustering is known to be sensitive to outliers. Our algorithms apply to the typical case where the set of input points lie in a

-dimensional space, and the distance is induced by the Euclidean norm.111E.g., all data sets used to evaluate the algorithms in Chierichetti et al. (2017) fall into this category.

To state the result formally, we need to introduce some notation. Consider a collection of points , where each point is colored either red or blue. For a subset of points , the balance of is defined as where and respectively denote the number of red and blue points in . Assuming , a clustering of is ()-fair if for every cluster , . In -median clustering, the goal is to find centers and partition the pointset into clusters centered at the selected centers such that the sum of the distances from each point point to its assigned center (i.e., the center of the cluster to which belongs) is minimized. In the -fair -median problem, all clusters are required to have balance at least . Our main result is summarized in the following theorem.

###### Theorem 1.1.

Let be the running time of an -approximation algorithms for the -median problem over points in . Then there exists an -time algorithm that given a point set and balance parameters , computes a -fair -median of whose cost is within a factor of from the optimal cost of -fair -median of .

The running time can be reduced further by applying dimensionality reduction techniques, see, e.g., Cohen et al. (2015); Makarychev et al. (2018) and the references therein.

We complement our theoretical analysis with empirical evaluation. Our experiments show that the quality of the clustering obtained by our algorithm is comparable to that of Chierichetti et al. (2017). At the same time, the empirical runtime of our algorithm scales almost linearly in the number of points, making it applicable to massive data sets (see Figure 1).

#### Related work.

Since the original paper of Chierichetti et al. (2017), there has been several followup works studying fair clustering. In particular, Rösner and Schmidt (2018) and Bercea et al. (2018) studied the fair variant of -center clustering (as opposed to -median in our case). Furthermore, the latter paper presented a “bi-criteria” approximation algorithm for -median and

-means under a somewhat different notion of fairness. However, their solution relies on a linear program that is a relaxation of an integer linear program with at least

variables, one for every pair of points. Thus, their algorithm does not scale well with the input size. Similarly, another algorithm proposed in Bera et al. (2019), requires solving linear programs with variables each.

The work most relevant to our paper is a recent manuscript by Schmidt et al. (2018), which proposed efficient streaming algorithms for fair -means (which is similar to -median studied here). Specifically, they give a near-linear time streaming algorithm for computing a core-set: a small subset such that solving fair clustering over yields an approximate solution for the original point-set . In order to compute the final clustering, however, they resort to a variant of the algorithm of Chierichetti et al. (2017), or another algorithm with a running time exponential in . Thus, our approach is complementary to theirs. In particular, our algorithm could be applied to the core-set generated by their method in order to reduce the space usage.

We note that the above algorithms guarantee constant approximation factors, as opposed to the logarithmic factor in our paper. As we show in the experimental section, this does not seem to affect the empirical quality of solutions produced by our algorithm. Still, designing a constant factor algorithm with a near-linear running time is an interesting open problem.

#### Possible settings of (r,b).

Chierichetti et al. (2017) gave -fairlet decomposition algorithms only for . This does not allow for computing a full decomposition of the pointset into well-balanced fairlets if the numbers of red and blue points are close but not equal (for instance, if their ratio is 9:10). One way to address this could be to downsample the larger set in order to make them have the same cardinality and then compute a -fairlet decomposition. The advantage of our approach is that we do not disregard any, even random, part of the input. This may potentially lead to much better solutions, partially by allowing that the clusters are not ideally balanced. The general settings of and are also considered by Bercea et al. (2018).

#### Our techniques.

Our main contribution is to design a nearly-linear time algorithm for -fairlet decomposition for any integer values of . Our algorithm has two steps. First, it embeds the input points into a tree metric called HST (intuitively, this is done by computing a quadtree decomposition of the point set, and then using the distances in the quadtree). In the second step it solves the fairlet decomposition problem with respect to the new distance function induced by HST. The distortion of the embedding into the HST accounts for the factor in the approximation guarantee.

Once we have the HST representation of the pointset, the high-level goal is to construct “local” -fairlets with respect to the tree. To this end, the algorithm scans the tree in a top-down order. In each node of the tree, it greedily partitions the points into fairlets so that the number of fairlets whose points belong to subtrees rooted at different children of is minimized. In particular, we prove that minimizing the number of such fairlets (which we refer to as the Minimum Heavy Point problem) leads to an -approximate -fairlet decomposition with respect to the distance over the tree.

## 2 Preliminaries

###### Definition 2.2 (Fairlet Decomposition).

Suppose that is a collection of points such that each is either colored red or blue. Moreover, suppose that for some integers such that . A clustering of is an -fairlet decomposition if (a) each point belongs to exactly one cluster , (b) for each , , and (c) for each , .

#### Probabilistic metric embedding.

A probabilistic metric is defined as a set of metrics

along with a probability distribution of support size

denoted by such that . For any finite metric and probabilistic metric , an embedding has distortion , if:

• for all and , ,

• .

###### Definition 2.3 (γ-Hst).

A tree rooted at vertex is a hierarchically well-separated tree (-HST) if all edges of have non-negative weights and the following two conditions hold:

1. The (weighted) distances from any node to all its children are the same.

2. For each node , the distance of to its children is at most times the distance of to its parent.

We build on the following result due to Bartal (1996), which gives a probabilistic embedding from to a -HST. Our algorithm explicitly computes this embedding which we describe in more detail in the next section. For a proof of its properties refer to Indyk (2001) and the references therein. In this paper, we assume that the given pointset has aspect ratio (i.e. the ratio between the maximum and minimum distance is ).

###### Theorem 2.4 (Bartal (1996)).

Any finite metric space on points in can be embedded into probabilistic metric over -HST metrics with distortion in time.

## 3 High-level Description of Our Algorithm

Our algorithm for -fair -median problem in Euclidean space follows the high-level approach of Chierichetti et al. (2017): it first computes an approximately optimal -fairlet decomposition for the input point set (see Algorithm 1). Then, in the second phase, it clusters the ()-fairlets produced in the first phase into clusters (see Algorithm 2). Our main contribution is designing a scalable algorithm for the first phase of this approach, namely ()-fairlet decomposition.

#### Preprocessing phase: embedding to γ-Hst.

An important step in our algorithm is to embed the input pointset into a -HST (see Section 2 for more details on HST metrics). To this end, we exploit the following standard construction of -HST using randomly shifted grids.

Suppose that all points in lie in . We generate a random tree (which is a -HST embedding of ) recursively. We translate the -dimensional hypercube

via a uniformly random shift vector

. It is straightforward to verify that all points in are enclosed in . We then split each dimension of into equal pieces to create a grid with cells. Then we proceed recursively with each non-empty cell to create a hierarchy of nested -dimensional grids with levels (each cell in the final level of the recursion either contains exactly one point of or has side length ). Next, we construct a tree corresponding to the described hierarchy nested -dimensional grids as follows. Consider a cell in the -th level (level denote the initial hypercube ) of the hierarchy. Let denote the trees constructed recursively for each non-empty cells of . Denote the root of each tree by . Then we connect (corresponding to cell ) to each of with an edge of length proportional to the diameter of (i.e., ).

Note that the final tree generated by the above construction is a -HST: on each path from the root to a leaf, the length of consecutive edges decrease exponentially (by a factor of ) and the distance from any node to all of its children are the same. Moreover, we assume that .

#### Phase 1: computing (r,b)-fairlet decomposition.

This phase operates on the probabilistic embedding of the input into a -HST from the preprocessing phase, where . The distortion of the embedding is . Additionally, we augment each node with integers and denoting the number of red and blue points, respectively, in the subtree rooted at .

#### Step 1.

Compute an approximately minimum number of points that are required to be removed from the children of so that (1) the set of points contained by each child becomes -balanced, and (2) the union of the set of removed points is also -balanced. More formally, we solve Question 3.6 approximately (recall that for each child , and respectively denotes the number of red and blue points in ).

###### Definition 3.5 (Heavy Point).

A point is heavy with respect to if it belongs to a fairlet such that . For each fairlet , denotes the least common ancestor (lca) of the points contained in in .

###### Question 3.6 (Minimum Heavy Points Problem).

Suppose that is a node in . For each corresponding to non-empty children of , let be respectively the number of red and blue points that are removed from . The goal is to minimize such that the following conditions hold:

1. for each , is ()-balanced.

2. is ()-balanced.

#### Step 2.

After computing , for each , remove an arbitrary set of red and blue points from and add them to . Then, output an arbitrary -fairlet decomposition of points which is guaranteed to be -balanced by Step 1.

#### Step 3.

For each corresponding to a non-empty child of , run which is guaranteed to be -balanced by Step 1.

Here is the main guarantee of our approach in the first step (i.e., ()-fairlet decomposition).

###### Theorem 3.7.

There exists an time algorithm that given a point set and balance parameters , computes an -fairlet decomposition of with respect to whose expected cost is within factor of the optimal -fairlet decomposition of in expectation.

#### Phase 2: merging (r,b)-fairlets into k clusters.

In this phase, we essentially follow the same approach as Chierichetti et al. (2017).

###### Theorem 3.8 (Fairlet to Fair Clustering).

Suppose that is an -approximate -fairlet decomposition of . Then, ClusterFairlet returns an -approximate -fair -median clustering of where denotes the approximation guarantee of the -median algorithm invoked in ClusterFairlet.

###### Proof:

For a pointset , let and respectively denote an optimal -fair -median and an optimal -fairlet decomposition of . It is straightforward to see that for any set of point , and in particular,

 cost(Q)≤α⋅cost(\textscOPTk%−fair(P)). (1)

Let denote the set of the centers of fairlets in . For a set of points , let denotes an optimal -median clustering of (note that there is not fairness requirement). Since , the optimal -median cost of is smaller than the optimal -median cost of . Since contains at most copies of each point of , by assigning all copies of each point in to the center of in an optimal -median clustering of ,

 cost(\textscOPTk-median(¯¯¯¯P)) ≤(r+b)⋅cost(\textscOPTk-median(N)) ≤(r+b)⋅cost(\textscOPTk-median(P)). (2)

As ClusterFairlet returns a -approximate -median clustering of , and by (1)-(2), the cost of the clustering constructed by ClusterFairlet is

Since the distance of each point to the center of its cluster in is less than the sum of its distance to the center of its fairlet in and the distance of to its center in , we can bound the cost of in terms of the costs of and as follows:

 cost(C∗) ≤cost(Q)+cost(C) ≤α⋅cost(\textscOPTk-fair(P)) ⊳By~{}(???) +β⋅cost(\textscOPTk-median(¯¯¯¯P)) ≤α⋅cost(\textscOPTk-fair(P)) +β⋅(r+b)⋅cost(\textscOPTk-% median(P)) ⊳By~{}(???) ≤(α+β⋅(r+b))⋅cost(\textscOPTk-fair(P))

Finally, Theorem 3.7 and 3.8 together imply Theorem 1.1.

## 4 Fairlet Decomposition: a Top-down Approach on γ-Hst

In this section, we provide a complete description of the first phase in our -fair -median algorithm (described in Section 3), namely our scalable ()-fairlet decomposition algorithm.

The first step in our algorithm is to embed the input point set into a -HST (for a value of to be determined later in this section). Once we build a -HST embedding of the input points , the question is how to partition the points into -fairlets. We assume that each node is augmented with extra information and respectively denoting the number of red and blue points in the subtree rooted at .

To compute the total cost of a fairlet decomposition, it is important to specify the clustering cost model (e.g., -median, -center). Here, we define to denote the cost of a fairlet (or cluster) with respect to the cost function of -median clustering: for any subset of points , where denotes the distance of in .

In this section, we design a fast fairlet decomposition algorithm with respect to .

###### Theorem 4.9.

There exists an time algorithm that given an -HST embedding of the point set and balance parameters , computes an -approximate -fairlet decomposition of with respect to on .

Thus, by Theorem 4.9 and the bound on the expected distortion of embeddings into HST metrics (Theorem 2.4), we can prove Theorem 3.7.

###### Proof of

Theorem 3.7. We first embed the points into an -HST and then perform the algorithm guaranteed in Theorem 4.9. By Theorem 2.4, the expected distortion of our embedding to is and by Theorem 4.9, there exists an algorithm that computes an -approximate fairlet-decomposition of with respect to distances in . Hence, the overall algorithm achieves -approximation.

Since the embedding can be constructed in time and the fairlet-decomposition algorithm of Theorem 4.9 runs in near-linear time, the overall algorithm also runs in .

Before describing the algorithm promised in Theorem 4.9, we define a modified cost function which is a simplified variant of and is particularly useful for computing the cost over trees. Consider a -HST embedding of denoted by and assume that is a fairlet decomposition of . Moreover, denotes the height of in . For each fairlet , is defined as

 costmed(D) :=∑q∈Dd(lca(D),q)=Θ(|D|⋅γh(lca(D))). (3)

In particular, relaxes the task of finding “the best center in fairlets” and at the same time, its value is within a small factor of .

###### Claim 4.10.

Suppose that is a -HST embedding of the set of points . For any -fairlet of , where the distance function is defined w.r.t. .

In the rest of this section we prove the following result which together with Claim 4.10 imply Theorem 4.9.

###### Lemma 4.11.

There exists a near-linear time algorithm that given an -HST embedding of the point set and balance parameters , computes an -approximate -fairlet decomposition of with respect to on .

###### Lemma 4.12.

For any tree with the root vertex , the number of heavy points with respect to in the ()-fairlet decomposition constructed by is at most times the minimum number of heavy points in any valid ()-fairlet decomposition of .

We prove Lemma 4.12 in Section 4.1. Here, we show that the overall algorithm, FairletDecomposition constructs an -approximate ()-fairlet decomposition with respect to .

###### Proof of

Lemma 4.11. The proof is by induction on height of in . The base case is when is a leaf node in and the algorithm trivially finds an optimal solution in this case. Suppose that the induction hypothesis holds for all vertices of at height . Here, we show that the statement holds for the vertices of at height as well.

Let OPT denote an optimal ()-fairlet decomposition of the points in with respect to . Next, we decompose OPT into parts: and . For each , denotes the set of fairlets in OPT whose lca are in . Moreover, denotes the set of heavy fairlets with respect to and denotes the set of heavy points with respect to in OPT. Lastly, denotes the set of heavy points with respect to in OPT that are contained in .

Let sol denote the solution returned by FairletDecomposition. Similarly, we decompose sol into parts: and . Moreover, denotes the set of heavy points with respect to in sol and for each , denotes the set of heavy points with respect to in sol that are contained in .

###### Claim 4.13.

For each , there exists an -fairlet decomposition of of cost at most where is the set of points contained in .

###### Proof:

Consider the fairlet decomposition on . A fairlet is affected if it contains a point .

We define the set of affected points as to denote the union of the points in the affected fairlets (i.e., ) and the set (whose points do not belong to any of fairlets in ).

Next, we bound the cost of the fairlet decomposition which is constructed by augmenting the set of fairlets with the set of affected points . Let denote the set of affected points . We augment the fairlet decomposition in three steps:

#### Step 1.

In this step, we create as many -balanced fairlets using the affected points only. Note that the contribution of each point involved in such fairlets is where denotes the distance of from the leaves in . Let denote the set of affected points that do not join any fairlets at the end of this step. Note that all points in are of the same color .

#### Step 2:

Next, we add as many points of as possible to the existing fairlets in while preserving the -balanced property. Now the extra cost incurred by each points of that joins a fairlet in this step is at most . Let be the set of points that do not belong to an fairlets by the end of the second phase. Note that at the end of this step, if is non-empty, then all fairlets are maximally-balanced -dominant (a fairlet is maximally-balanced -dominant if (1) in , the number of points of color are larger than the number of points in color , (2) the set is -balanced, and (3) adding a point of color to makes it unbalanced).

#### Step 3:

Finally, we show that by mixing the points of at most existing fairlets with the set , we can find an -balanced fairlet decomposition of the involved points and the contribution of each such point to the total cost is at most . Note that since the set of all points we are considering is -balanced, not all of the so far constructed fairlets are saturated (i.e., has size exactly ). In particular, we show that there exists a set of non-saturated fairlets of size at most whose addition to constitutes a -balanced set. For each fairlet ,

 |cD|

where and respectively denotes the set of points of color and in . This implies that after picking at most non-saturated fairlets (i.e., the fairlets in ),

 b⋅|cX|≤r⋅|¯¯cX|−b⋅|Q2| ⇒b⋅(|cX|+|Q2|)≤r⋅|¯¯cX|,

where and respectively denotes the set of points of color and in . Hence, the set of points is -balanced. Moreover, the cost of this step is at most .

Altogether, there exists a fairlet decomposition of of cost at most

 cost(\textscOPTi)+|Q0∖Q1|⋅hT(vi) +|Q1∖Q2|⋅(r+b)⋅hT(vi) +|Q2|⋅b⋅(r+b)⋅hT(vi) ≤cost(\textscOPTi)+|Q0|⋅b⋅(r+b)⋅hT(vi) ≤cost(\textscOPTi) +(|Hi\textscOPT|+|Hi\textscsol|⋅(r+b))⋅(r2+b2)⋅γh−1

Hence, by the induction hypothesis, for each ,

 cost(\textscsoli) ≤c⋅(r2+b2)⋅(cost(\textscOPTi) +(|Hi\textscOPT|+|Hi\textscsol|⋅(r+b))⋅(r2+b2)⋅γh−1) (4)

Next, we bound the cost of sol by Lemma 4.12 and (4) as follows:

 cost(\textscsol) =cost(\textscsolH)+∑i∈[γd]cost(\textscsoli) ≤ηH⋅(r2+b2)⋅cost(\textscOPTH) +c⋅(r2+b2)⋅(ηH(r+b)5γ⋅cost(\textscOPTH) +∑i∈[kd]cost(\textscOPTi)) ≤c⋅(r2+b2)⋅cost(\textscOPT) +(ηH−c2)⋅(r2+b2)⋅cost(\textscOPTH) ⊳By setting γ:=2ηH(r+b)5 ≤c⋅(r2+b2)⋅cost(\textscOPT)⊳c≥2ηH

### 4.1 Description of Step 1: Minimizing the Number of Heavy Points

In this section, we show that MinHeavyPoints algorithm invoked by FairletDecomposition finds an -approximate solution of Minimum Heavy Points problem.

The high-level overview of MinHeavyPoints is as follows. For any subset of points , we can compute in what the maximal size -balanced subset of is: w.l.o.g. suppose that and . If , the collection is -balanced. Otherwise, it suffices to greedily pick maximal size -fairlets (see procedure UnbalancedPoints for the formal algorithm). This simple observation implies a lower bound on the size of any optimal solution of Heavy Points Minimization with respect to and we use this value to bound the approximation guarantee of MinHeavyPoints algorithm.

###### Claim 4.14.

UnbalancedPoints correctly computes the minimum number of points that is required to be removed from so that the remaining points become -balanced. Moreover, the solution returned by the procedure only removes points form a single color class.

For each , let be the output of UnbalancedPoints.

###### Corollary 4.15.

Any -fairlet decomposition of the points in has at least heavy points.

#### Stage 1: minimum number of heavy points.

If red points together with blue points form an -balanced collection, then MinHeavyPoints technically terminates at the end of stage and the solution returned by MinHeavyPoints achieves the minimum possible number of heavy points. However, in general, the collection with red points and may not form an -balanced collection. Next, we show that we can always pick at most additional heavy points and keep both all subtrees rooted at children of and the set of heavy points -balanced.

Another structure we will refer to in the rest of this section is saturated ()-fairlets. A fairlet is a saturated -fairlet if it has exactly points; points from color and points from color .

#### Stage 2: Adding free points.

If the “must-have” heavy points are not -balanced, then one color is dominant. For a color class , a collection of points is -dominant if . Moreover, the collection is minimally-balanced -dominant if is -balanced but it will be no longer -balanced even if we remove a single point of color .

Let be the dominant color in the heavy points. Then, we inspect all children of and if there exits a child in which is dominant, we borrow as many points of color as we can (we need to keep the subtree -balanced, see ExtraPoint procedure) till either the set of heavy points becomes -balanced or all subtrees rooted at children of become minimally-balanced -dominant. It is straightforward to show that at most points of color will be borrowed from the children of in this phase.

###### Lemma 4.16.

Suppose that the set of heavy points is -dominant. If the set of heavy points is not -balanced at the end of stage 2, then for each , the set of points in the subtree rooted at is minimally-balanced -dominant.

###### Corollary 4.17.

Suppose that the set of heavy points is -dominant. If the set of heavy points is not -balanced at the end of stage 2, then for each


text:
Applications of the derivative. Strictly monotonic functions

How I can prove this?

Let $$f(x) = \sin x + \frac{x^2}{2} - 2x.$$

Show that $f$ has only one critical number in the interval $[2, 3]$.

It belongs to the chapter on applications of the derivative. Section: Relative extrema of real functions.

-

The definition of "critical point" is that it is a point where the function is defined, but the derivative is either equal to $0$ or undefined.

So, let's try taking the derivative and staring at it, perhaps we can "tell" immediately that there is one and only one critical point in $[2,3]$.

\begin{align*} f(x) &= \sin x + \frac{x^2}{2} -2x\\ f'(x) &= \cos x + x - 2. \end{align*} This is defined everywhere, so the only critical points will be stationary points.

So... can we just "tell" that $f'(x)$ takes the value $0$ only once on $[2,3]$ by staring at it? Hmmm... That doesn't seem easy to do (you could note that $x-2$ takes the values from $0$ to $1$, and that $\cos x$ is negative and decreasing, but that tells you that $f'(x)$ is negative at $2$ and positive at $3$, hence $f$ has at least one critical point by the Intermediate Value Theorem since $f'$ is continuous, but it doesn't tell you it has exactly one).

What else can we do? How about seeing whether this function is strictly monotone? As noted parenthetically, $f'(2)\lt 0$ and $f'(3)\gt 0$. If $f'(x)$ is strictly monotone on $[2,3]$, then it goes through zero exactly once.

-
A very clear answer. And to prove that $f'$ is strictly increasing enough to calculate $f''$ and verify that is positive. Thanks so much. Served me well. =) – mathsalomon Aug 19 '11 at 4:29
@mathsalomon: If you found Arturo's answer helpful, you can vote it up by clicking on the up arrow. You can vote up to 30 times per day. Also you can do this on other questions when you read an answer which is particularly interesting or helpful. (you can even up vote questions!) – Eric Naslund Aug 19 '11 at 4:52
@Eric Naslund: Thanks Eric. – mathsalomon Aug 19 '11 at 7:17
@mathsalomon: Note that you can only "accept" one answer (I mention it because you seem to have switched two or more times between my answer and Eric's). That's the "checkmark" on the left, under the vote counter. You can change your mind, but only one answer can be the "accepted answer" at a time. If you are unsure which answer was, in your mind, the most helpful or clearest, then wait a while before accepting. – Arturo Magidin Aug 19 '11 at 15:04

Hint: The second derivative is positive on $[2,3]$. To see why, notice $$f''(x) =-\sin x+1>0$$ and that $|\sin x |<1$ on $[2,3]$.

This means that the derivative $f^'(x)$ is increasing on $[2,3]$, and you can use this idea to find that there is at most one critical number. The intermediate value theorem tells you there is exactly one.

-
I think you mean "negative"? – Arturo Magidin Aug 19 '11 at 3:36
He means $-\sin x + 1$ is positive. – Robert Israel Aug 19 '11 at 3:38
@Arturo: Thanks, corrected. – Eric Naslund Aug 19 '11 at 3:38
@Robert: Exactly. The way I had worded it earlier was very strange so I fixed it now. – Eric Naslund Aug 19 '11 at 3:41
Good answer. Thanks. – mathsalomon Aug 19 '11 at 4:32


text:
IS² for Bayesian inference

“…the method of Approximate Bayesian Computation (ABC) may be used to estimate unbiasedly an approximation to the likelihood.”

Minh-Ngoc Tran, Marcel Scharth, Michael Pitt and Robert Kohn arXived a paper on using an unbiased estimate of the likelihood in lieu of the genuine thing and still getting convergence to the right thing. While the spirit of the paper is in the same spirit as the fundamental paper of  Andrieu and Roberts (2009, AoS, somewhat surprisingly missing from the reference), comparing the asymptotic efficiency of using an estimate versus using the genuine likelihood, my attention was distracted by the above quote. This is the only sentence (besides the abstract) where ABC is mentioned and I was a bit confused: ABC is used to estimate an approximation to the likelihood, for sure, converging to

$\int_{d(x,x^\text{obs})\le\varepsilon} f(x|\theta)\,\text{d}\theta$

as the number of pseudo-datasets grows to infinity and it is unbiased on this sense, but this is not the reason for using ABC, as the ABC pseudo-likelihood above is the (by)product of the methodology rather than the genuine quantity of interest. Reading the sentence too fast gave me the feeling that ABC did produce an unbiased approximation to the genuine likelihood! Distracted I was, since this is not at all the point of the paper! However, I would be curious to see how it applies to ABC.

The core result is the convergence of an importance sampling estimator using a likelihood estimated by importance sampling (hence the IS², also inspired by SMC²),. The trick in the proof is to turn the computation of  the likelihood estimand into the production of an (unobserved or “implicitly generated”) auxiliary variable and then to rewrite the original estimator as a genuine importance estimator. (This seems to imply the derivation of an independent importance sampling estimator of the likelihood at each iteration, right?) Standard convergence results then follow, except that the asymptotic variance has an extra term. And except that the estimator of the likelihood does not have to converge, i.e. can keep a fixed number of terms and a positive variance. The second part of the paper establishes that using an estimate degrades the asymptotic variance.

5 Responses to “IS² for Bayesian inference”

1. Not always obvious when the obvious is obvious.

With a large sample from the (exact) prior and a large sample from the (approximate) posterior does seem obvious that you should be able to get a (good) approximation of the posterior/prior.

• K: I am still reluctant to talk of a real or exact prior. Your large sample from the prior means we are drifting towards frequentism…

• To me, a prior is just a statistician’s representation (model) of how nature determined an unknown and I can know exactly what my representation is and work with it for some purpose.

My favourite story in this regard is the angry husband and Picasso.

Husband: Picasso that painting you did of my wife looks nothing like her!
Picasso: Really – what does she look like?
Husband: I have a picture of her in my wallet – see!
Picasso: My she is awfully tiny!!

Also, I thought having anything from a prior kept one away from frequentism (unless one could prove it had absolutely no impact).

2. The logic is almost circular: as an approximation of the likelihood, take the expected value of your favourite ABC scheme. Then by definition, ABC provides an unbiased estimator of that approximation… The same could be said of any approximate method.

• This was my first impression but I was hoping for something deeper…

This site uses Akismet to reduce spam. Learn how your comment data is processed.


text:
DSBCentre

The central position of interest in a dual sideband spectrum

Description:

This attribute specifies the central position of interest in a dual sideband spectrum. Its sole use is to determine the local oscillator frequency (the frequency which marks the boundary between the lower and upper sidebands). See the description of the IF (intermediate frequency) attribute for details of how the local oscillator frequency is calculated. The sideband containing this central position is referred to as the " observed" sideband, and the other sideband as the " image" sideband.

The value is accessed as a position in the spectral system represented by the SpecFrame attributes inherited by this class, but is stored internally as topocentric frequency. Thus, if the System attribute of the DSBSpecFrame is set to " VRAD" , the Unit attribute set to " m/s" and the StdOfRest attribute set to " LSRK" , then values for the DSBCentre attribute should be supplied as radio velocity in units of " m/s" relative to the kinematic LSR (alternative units may be used by appending a suitable units string to the end of the value). This value is then converted to topocentric frequency and stored. If (say) the Unit attribute is subsequently changed to " km/s" before retrieving the current value of the DSBCentre attribute, the stored topocentric frequency will be converted back to LSRK radio velocity, this time in units of " km/s" , before being returned.

The default value for this attribute is 30 GHz.

Type:
Floating point.

Applicability

DSBSpecFrame
All DSBSpecFrames have this attribute.

Note

• The attributes which define the transformation to or from topocentric frequency should be assigned their correct values before accessing this attribute. These potentially include System, Unit, StdOfRest, ObsLon, ObsLat, ObsAlt, Epoch, RefRA, RefDec and RestFreq.


text:
Subscribe
Issue No.08 - Aug. (2013 vol.19)
pp: 1386-1404
H. Bhatia , Lawrence Livermore Nat. Lab., Univ. of Utah, Livermore, CA, USA
G. Norgard , Numerica, Fort Collins, CO, USA
V. Pascucci , Sci. Comput. & Imaging Inst. (SCI), Univ. of Utah, Salt Lake City, UT, USA
Peer-Timo Bremer , Lawrence Livermore Nat. Lab., Univ. of Utah, Livermore, CA, USA
ABSTRACT
The Helmholtz-Hodge Decomposition (HHD) describes the decomposition of a flow field into its divergence-free and curl-free components. Many researchers in various communities like weather modeling, oceanology, geophysics, and computer graphics are interested in understanding the properties of flow representing physical phenomena such as incompressibility and vorticity. The HHD has proven to be an important tool in the analysis of fluids, making it one of the fundamental theorems in fluid dynamics. The recent advances in the area of flow analysis have led to the application of the HHD in a number of research communities such as flow visualization, topological analysis, imaging, and robotics. However, because the initial body of work, primarily in the physics communities, research on the topic has become fragmented with different communities working largely in isolation often repeating and sometimes contradicting each others results. Additionally, different nomenclature has evolved which further obscures the fundamental connections between fields making the transfer of knowledge difficult. This survey attempts to address these problems by collecting a comprehensive list of relevant references and examining them using a common terminology. A particular focus is the discussion of boundary conditions when computing the HHD. The goal is to promote further research in the field by creating a common repository of techniques to compute the HHD as well as a large collection of example applications in a broad range of areas.
INDEX TERMS
Vectors, Communities, Boundary conditions, Visualization, Physics, Conferences, Helmholtz-Hodge decomposition, Vector fields, incompressibility, boundary conditions
CITATION
H. Bhatia, G. Norgard, V. Pascucci, Peer-Timo Bremer, "The Helmholtz-Hodge Decomposition—A Survey", IEEE Transactions on Visualization & Computer Graphics, vol.19, no. 8, pp. 1386-1404, Aug. 2013, doi:10.1109/TVCG.2012.316
REFERENCES
 [1] R. Abraham, J.E. Marsden, and T. Ratiu, Manifolds, Tensor Analysis and Applications, vol. 75, Applied Math. Science, second ed. Springer-Verlag, 1988. [2] E. Ahusborde, M. Azaiez, and J.-P. Caltagirone, "A Primal Formulation for the Helmholtz Decomposition," J. Computational Physics, vol. 225, no. 1, pp. 13-19, 2007. [3] K. Aki and P.G. Richards, Quantitative Seismology. Univ. Science Books, 2002. [4] M. Akram and V. Michel, "Regularisation of the Helmholtz Decomposition and its Application to Geomagnetic Field Modelling," Int'l J. Geomath., vol. 1, no. 1, pp. 101-120, 2010. [5] C. Amrouche, C. Bernardi, M. Dauge, and V. Girault, "Vector Potentials in Three-Dimensional Nonsmooth Domains," Math. Methods in the Applied Sciences, vol. 21, pp. 823-864, 1998. [6] H. Aref, N. Rott, and H. Thomann, "Gröbli's Solution of the Three-Vortex Problem," Ann. Rev. Fluid Mechanics, vol. 24, pp. 1-21, 1992. [7] G. Arfken, Mathematical Methods for Physicists, second ed. Academic Press, 1970. [8] G. Auchmuty, "Potential Representation of Incompressible Vector Fields," Nonlinear Problems in Applied Mathematics, pp. 43-49, SIAM, 1995. [9] J.B. Bell, P. Colella, and H.M. Glaz, "A Second Order Projection Method for the Incompressible Navier-Stokes Equations," J. Computational Physics, vol. 85, pp. 257-283, 1989. [10] J.B. Bell and D.L. Marcus, "A Second-Order Projection Method for Variable-Density Flows," J. Computational Physics, vol. 101, pp. 334-348, 1992. [11] H. Bhatia, G. Norgard, V. Pascucci, and P.-T. Bremer, "Comments on the 'Meshless Helmholtz-Hodge Decomposition'," IEEE Trans. Visualization and Computer Graphics, vol. 19, no. 3, pp. 527-528, Mar. 2013. [12] O. Blumenthal, "Über Die Zerlegung Unendlicher Vektorfelder," Mathematische Annalen, vol. 61, no. 2, 235-250, 1905. [13] H. Braun and A. Hauck, "Tomographic Reconstruction of Vector Fields," IEEE Trans. Signal Processing, vol. 39, no. 2, pp. 464-471, Feb. 1991. [14] R. Bridson, Fluid Simulation For Computer Graphics. A.K. Peters, 2008. [15] D.L. Brown, R. Cortez, and M.L. Minion, "Accurate Projection Methods for the Incompressible Navier-Stokes Equations," J. Computational Physics, vol. 168, pp. 464-499, 2001. [16] E.B. Bykhovskiy and N.V. Smirnov, On Orthogonal Expansions of the Space of Vector Functions Which Are Square-Summable over a Given Domain and the Vector Analysis Operators. Academy of Sciences USSR Press, 1960. [17] J. Caltagirone and J. Breil, "A Vector Projection Method for Solving the Navier-Stokes Equations," Comptes Rendus de l'Académie des Sciences - Series IIB - Mechanics-Physics-Astronomy, vol. 327, no. 11, pp. 1179-1184, 1999. [18] J. Cantarella, D. DeTurck, and H. Gluck, "Vector Calculus and the Topology of Domains in 3-Space," Am. Math. Monthly, vol. 109, no. 5, pp. 409-442, 2002. [19] A.J. Chorin, "A Numerical Method for Solving Incompressible Viscous Flow Problems," J. Computational Physics, vol. 2, pp. 12-26, 1967. [20] A.J. Chorin, "Numerical Solution of the Navier-Stokes Equations," Math. Computations, vol. 22, pp. 745-762, 1968. [21] A.J. Chorin, "On the Convergence of Discrete Approximations to the Navier-Stokes equations," Math. Computations, vol. 23, pp. 341-353, 1969. [22] A.J. Chorin and J.E. Marsden, A Mathematical Introduction to Fluid Mechanics. Springer, 1993. [23] F. Colin, R. Egli, and F. Lin, "Computing a Null Divergence Velocity Field Using Smoothed Particle Hydrodynamics," J. Computational Physics, vol. 217, no. 2, pp. 680-692, 2006. [24] R. Courant and D. Hilbert, Methods of Mathematical Physics. New York Univ., 1953. [25] R. Courant, E. Isaacson, and M. Rees, "On the Solution of Nonlinear Hyperbolic Differential Equations by Finite Differences," Comm. Pure and Applied Math., vol. 5, pp. 243-255, 1952. [26] S.J. Cummins and M. Rudman, "An SPH Projection Method," J. Computational Physics, vol. 152, pp. 584-607, 1999. [27] F.M. Denaro, "On the Application of the Helmholtz-Hodge Decomposition in Projection Methods for Incompressible Flows with General Boundary Conditions," Int'l J. Numerical Methods in Fluids, vol. 43, pp. 43-69, 2003. [28] E. Deriaz and V. Perrier, "Divergence-Free and Curl-Free Wavelets in 2D and 3D, Application to Turbuent Flows," J. Turbulence, vol. 7, no. 3, pp. 1-37, 2006. [29] E. Deriaz and V. Perrier, "Direct Numerical Simulation of Turbulence Using Divergence-Free Wavelets," Multiscale Modeling and Simulation, vol. 7, no. 3, pp. 1101-1129, 2008. [30] E. Deriaz and V. Perrier, "Orthogonal Helmholtz Decomposition in Arbitrary Dimension using Divergence-Free and Curl-Free Wavelets," Applied and Computational Harmonic Analysis, vol. 26, no. 2, pp. 249-269, 2009. [31] W. Weinan and J.G. Liu, "Projection Method I: Convergence and Numerical Boundary Layers," SIAM J. Numerical Analysis, vol. 32, no. 4, pp. 1017-1057, 1995. [32] R. Fedkiw, J. Stam, and H.W. Jensen, "Visual Simulation of Smoke," Proc. 28th Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH '01), pp. 15-22, 2001. [33] M. Fisher, P. Schröder, M. Desburn, and H. Hoppe, "Design of Tangent Vector Fields," ACM Trans. Graphics, vol. 26, no. 3,article 56, 2007. [34] N. Foster and D. Metaxas, "Realistic Animation of Liquids," Graphical Models and Image Processing, vol. 58, no. 5, pp. 471-483, 1996. [35] N. Foster and D. Metaxas, "Modeling the Motion of a Hot, Turbulent Gas," Proc. 24th Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH '97), pp. 181-188, 1997. [36] D. Fujiwara and H. Morimoto, "An $L_r$ Theorem of the Helmholtz Decomposition of Vector Fields," J. Faculty of Science, vol. 44, pp. 685-700, 1977. [37] E.J. Fuselier, "Refined Error Estimates for Matrix-Valued Radial Basis Functions," PhD thesis, Texas A & M Univ., 2006. [38] H. Gao, M. Mandal, G. Guo, and J. Wan, "Singular Point Detection using Discrete Hodge Helmholtz Decomposition in Fingerprint Images," Proc. IEEE Int'l Conf. Acoustics Speech and Signal Processing (ICASSP), pp. 1094-1097, 2010. [39] J. Geng and Z. Shen, "The Neumann Problem and Helmholtz Decomposition in Convex Domains," J. Functional Analysis, vol. 259, pp. 2147-2164, 2010. [40] D. Georgobiani, N. Mansour, A. Kosovichev, R. Stein, and Å. Nordlund, "Velocity Field Decomposition in 3D Numerical Simulations of Solar Turbulent Convection," NASA Center for Turbulence Research - Ann. Research Briefs, pp. 355-340, 2004. [41] D.J. Griffiths, Introduction to Electrodynamics, second ed. Addison Wesley, 1999. [42] Q. Guo, "Cardiac Video Analysis using the Hodge Helmholtz Field Decomposition," master's thesis, Dept. of Electrical and Computer Eng., Univ. of Alberta, 2004. [43] Q. Guo, M.K. Mandal, and M.Y. Li, "Efficient Hodge-Helmholtz Decomposition of Motion Fields," Pattern Recognition Letters, vol. 26, no. 4, pp. 493-501, 2005. [44] Q. Guo, M.K. Mandal, G. Liu, and K.M. Kavanagh, "Cardiac Video Analysis Using Hodge-Helmholtz Field Decomposition," Computers in Biology and Medicine, vol. 36, no. 1, pp. 1-20, 2006. [45] R. Guy and A. Fogelson, "Stability of Approximate Projection Methods on Cell-Centered Grids," J. Computational Physics, vol. 203, pp. 517-538, 2005. [46] F.H. Harlow and J.E. Welch, "Numerical Calculation of Time-Dependent Viscous Incompressible Flow of Fluid with Free Surface," Physics of Fluids, vol. 8, no. 12, pp. 2182-2189, 1965. [47] R. Hatton and H. Choset, "Optimizing Coordinate Choice for Locomoting Systems," Proc. IEEE Int'l conf. Robotics and Automation (ICRA), pp. 4493-4498, 2010. [48] W. Hauser, "On the Fundamental Equations of Electromagnetism," Am. J. Physics, vol. 38, no. 1, pp. 80-85, 1970. [49] W. Hauser, Introduction to the Principles of Electromagnetism. Addison-Wesley Educational Publishers Inc, 1971. [50] H. Helmholtz, "Über Integrale der Hydrodynamischen Gleichungen, Welche den Wirbelbewegungen Entsprechen," J. für die reine und angewandte Mathematik, vol. 1858, no. 55, pp. 25-55, Jan. 1858. [51] H. Helmholtz, "On Integrals of the Hydrodynamical Equations, which Express Vortex-Motion," Philosophical Magazine and J. Science, vol. 33, no. 226, pp. 485-512, 1867. [52] J. Hinkle, P.T. Fletcher, B. Wang, B. Salter, and S. Joshi, "4D MAP Image Reconstruction Incorporating Organ Motion," Proc. 21st Int'l Conf. Information Processing in Medical Imaging, (IPMI), 2009. [53] W. Hodge, The Theory and Applications of Harmonic Integrals. Cambridge Univ. Press, 1952. [54] M.S. Ingber and S.N. Kempka, "A Galerkin Implementation of the Generalized Helmholtz Decomposition for Vorticity Formulations," J. Computational Physics, vol. 169, no. 1, pp. 215-237, 2001. [55] T. Jie and Y. Xubo, "Physically-Based Fluid Animation: A Survey," Science in China Series F: Information Sciences, vol. 52, no. 1, pp. 1-17, 2007. [56] S.A. Johnson, J.F. Greenleaf, M. Tanaka, and G. Flandro, Acoustical Holography, vol. 7. Plenum Press, 1977. [57] D.D. Joseph, "Helmholtz Decomposition Coupling Rotational to Irrotational Flow of a Viscous Fluid," Proc. Nat'l Academy of Sciences of USA, vol. 103, no. 39, pp. 14272-14277, 2006. [58] J. Kim and P. Moin, "Application of a Fractional-Step Method to Incompressible Navier-Stokes Equations," J. Computational Physics, vol. 59, no. 2, pp. 308-323, 1985. [59] D.H. Kobe, "Helmholtz Theorem for Antisymmetric Second-Rank Tensor Fields and Electromagnetism with Magnetic Monopoles," Am. J. Physics, vol. 52, no. 4, pp. 354-358, 1984. [60] D.H. Kobe, "Helmholtz's Theorem Revisited," Am. J. Physics, vol. 54, no. 6, pp. 552-554, 1986. [61] K. Kodaira, "Harmonic Fields in Riemannian Manifolds," Annals of Math., vol. 50, pp. 587-665, 1949. [62] O.A. Ladyzhenskaja, The Mathematical Theory of Viscous Incompressible Flow. Gordon and Breach, 1963. [63] H. Lamb, Hydrodynamics, sixth ed. Cambridge Univ. Press, 1932. [64] F. Losasso, F. Gibou, and R. Fedkiw, "Simulating Water and Smoke with an Octree Data Structure," ACM Trans. Graphics, vol. 23, pp. 457-462, 2004. [65] L.B. Lucy, "A Numerical Approach to the Testing of the Fission Hypothesis," The Astronomical J., vol. 82, pp. 1013-1024, 1977. [66] I. Mac$\hat{\rm e}$ do and R. Castro, "Learning Divergence-Free and Curl-Free Vector Fields with Matrix-Valued Kernels," technical report, Instituto de Matemática Pura e Aplicada, Rio de Janeiro, Brazil, 2010. [67] N.N. Mansour, A. Kosovichev, D. Georgobiani, A. Wray, and M. Miesch, "Turbulence Convection and Oscillations in the Sun," Proc. SOHO14/GONG Workshop, "Helio- and Astero-Seismology: Towards a Golden Future," 2004. [68] S.F. McCormick, "The Finite Volume Method," Multilevel Adaptive Methods for Partial Differential Equations, chapter 3, vol. 6. SIAM, 1989. [69] C.A. Micchelli and M. Pontil, "On Learning Vector-Valued Functions," Neural Computation, vol. 17, pp. 177-204, 2005. [70] B.P. Miller, "Interpretations from Helmholtz Theorem in Classical Electromagnetism," Am. J. Physics, vol. 52, p. 948, 1984. [71] C. Min and F. Gibou, "A Second Order Accurate Projection Method for the Incompressible Navier-Stokes Equations on Non-Graded Adaptive Grids," J. Computational Physics, vol. 219, pp. 912-929, 2006. [72] C. Min, F. Gibou, and H.D. Ceniceros, "A Supra-Convergent Finite Difference Scheme for the Variable Coefficient Poisson Equation on Non-Graded Grids," J. Computational Physics, vol. 218, no. 1, pp. 123-140, 2006. [73] Y. Mochizuki and A. Imiya, "Spatial Reasoning for Robot Navigation Using the Helmholtz-Hodge Decomposition of Omnidirectional Optical Flow," Proc. 24th Int'l Conf. Image and Vision Computing (IVCNZ), pp. 1-6, 2009. [74] J.J. Monaghan, "Smoothed Particle Hydrodynamics," Ann. Rev. of Astronomy and Astrophysics, vol. 30, pp. 543-574, 1992. [75] L. Morino, "Helmholtz Decomposition Revisited: Vorticity Generation and Trailing Edge Condition," Computational Mechanics, vol. 1, pp. 65-90, 1986. [76] F.J. Narcowich and J.D. Ward, "Generalized Hermite Interpolation Via Matrix-Valued Conditionally Positive Definite Functions," Math. of Computations, vol. 63, no. 208, pp. 661-687, 1994. [77] D.Q. Nguyen, R. Fedkiw, and H.W. Jensen, "Physically based Modeling and Animation of Fire," ACM Trans. Graphics, vol. 21, pp. 721-728, 2002. [78] S.J. Norton, "Tomographic Reconstruction of 2-D Vector Fields: Applications to Flow Imaging," Geophysics J. Int'l, vol. 97, no. 1, pp. 161-168, 1988. [79] S.J. Norton, "Unique Tomographic Reconstruction of Vector Fields Using Boundary Data," IEEE Trans. Image Processing, vol. 1, no. 3, pp. 406-412, July 1992. [80] B. Palit, A. Basu, and M. Mandal, "Applications of the Discrete Hodge-Helmholtz Decomposition to Image and Video Processing," Proc. First Int'l Conf. Pattern Recognition and Machine Intelligence, S. Pal, S. Bandyopadhyay, and S. Biswas, eds., pp. 497-502, 2005. [81] F. Petronetto, A. Paiva, M. Lage, G. Tavares, H. Lopes, and T. Lewiner, "Meshless Helmholtz-Hodge Decomposition," IEEE Trans. Visualization and Computer Graphics, vol. 16, no. 2, pp. 338-342, Mar./Apr. 2010. [82] M. Pharr and G. Humphreys, Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann Publishers, Inc., 2004. [83] K. Polthier and E. Preuß, "Variational Approach to Vector Field Decomposition," Proc. Eurographics Workshop Scientific Visualization, 2000. [84] K. Polthier and E. Preuß, "Identifying Vector Fields Singularities Using a Discrete Hodge Decomposition," Mathematical Visualization III, H.C. Hege, K. Polthier, eds., pp. 112-134, Springer, 2003. [85] S. Popinet, "A Tree-Based Adaptive Solver for the Incompressible Euler Equations in Complex Geometries," J. Computational Physics, vol. 190, pp. 572-600, 2003. [86] J.L. Prince, "Convolution Backprojection Formulas for 3-D Vector Tomography with Application to MRI," IEEE Trans. Image Processing, vol. 5, no. 10, pp. 1462-1472, Oct. 1996. [87] R. Scharstein, "Helmholtz Decomposition of Surface Electric Current in Electromagnetic Scattering Problems," Proc. 23rd Southeastern Symp. System Theory, pp. 424-426, 1991. [88] N. Schleifer, "Differential Forms as a Basis for Vector Analysis - with Applications to Electrodynamics," Am. J. Physics, vol. 51, no. 45, p. 1983, 1983. [89] G. Schwarz, Hodge Decomposition - A Method for Solving Boundary Value Problems. Springer, 1995. [90] J.M. Solomon and W.G. Szymczak, "Finite Difference Solutions for the Incompressible Navier-Stokes Equations Using Galerkin Techniques," Proc. Fifth IMACS Int'l Symp. Computer Methods for Partial Differential Equations, June 1984. [91] W. Sprössig, "On Helmholtz Decompositions and their Generalizations - An Overview," Math. Methods in the Applied Sciences, vol. 33, pp. 374-383, 2010. [92] J. Stam, "Stable Fluids," Proc. ACM SIGGRAPH '99, pp. 121-128, 1999. [93] J. Stam, "A Simple Fluid Solver Based on the FFT," J. Graphics Tools, vol. 6, pp. 43-52, 2002. [94] J. Stam and E. Fiume, "Depicting Fire and Other Gaseous Phenomena Using Diffusion Processes," Proc. ACM SIGGRAPH '95, pp. 129-136, 1995. [95] R. Stein and Å. Nordlund, "Realistic Solar Convection Simulations," Solar Physics, vol. 192, pp. 91-108, 2000. [96] A.B. Stephens, J.B. Bell, J.M. Solomon, and L.B. Hackerman, "A Finite Difference Galerkin Formulation for the Incompressible Navier-Stokes Equations," J. Computational Physics, vol. 53, pp. 152-172, 1984. [97] Y. Tong, S. Lombeyda, A. Hirani, and M. Desbrun, "Discrete Multiscale Vector Field Decomposition," ACM Trans. Graphics, vol. 22, no. 3, pp. 445-452, 2003. [98] J. van Kan, "A Second-Order Accurate Pressure-Correction Scheme for Viscous Incompressible Flow," SIAM J. Scientific and Statistical Computing, vol. 7, no. 3, pp. 870-891, 1986. [99] K. Wang Weiwei, Y. Tong, M. Desburn, and P. Schröder, "Edge Subdivision Schemes and the Construction of Smooth Vector Fields," ACM Trans. Graphics, vol. 25, no. 3, pp. 1041-1048, 2006. [100] H. Weyl, "The Method of Orthogonal Projection in Potential Theory," Duke Math. J., vol. 7, no. 7, pp. 411-444, 1940. [101] A. Wiebel, "Feature Detection in Vector Fields Using the Helmholtz-Hodge Decomposition," Diploma thesis, Diplomarbeit, Univ. Kaiserslautern, 2004. [102] A. Wiebel, C. Garth, and G. Scheuermann, "Computation of Localized Flow for Steady and Unsteady Vector Fields and its Applications," IEEE Trans. Visualization and Computer Graphics, vol. 13, no. 4, pp. 641-651, July/Aug. 2007.


text:
# Worksheet on Finding the Unknown Angle Using Trigonometric Identities

In Worksheet on finding the unknown angle using Trigonometric identities we will solve various types of practice questions on solving equation.

Here you will get 11 different types of solving equation using trigonometric identities questions with some selected questions hints.

1. Solve the equation 2 cos2 θ = 1; where 0° < θ < 90°.

2. Solve the equation $$\sqrt{3}$$ tan θ = 1; where 0° < θ < 90°.

3. Solve the equation 2 cos (2θ) = 1; where 0° < θ < 90°.

4. Solve the equation 2 cos2 θ - 11 cos θ + 5 = 0; where 0° < θ < 90°.

5. Solve the equation 2 sin2 θ + cos θ - 2 = 0; where 0° < θ < 90°.

6. Solve the equation 2 sec2 θ = 5 tan θ; where 0° < θ < 90°.

Hint: 2 sec2 θ = 5 tan θ

⟹ 2 (1 + tan2 θ) = 5 tan θ

⟹ 2 + 2 tan2 θ = 5 tan θ

⟹ 2 tan2 θ - 5 tan θ + 2 = 0

⟹ 2 tan2 θ - 4 tan θ - tan θ + 2 = 0

⟹ 2 tan θ (tan θ – 2) – 1 (tan θ – 2) = 0

⟹ (tan θ – 2)(2 tan θ – 1) = 0

7. Are the following identities? If not, solve for θ, where 0° < θ < 90°).

(i) $$\frac{ cos θ}{1 - sin θ}$$ + $$\frac{ cos θ}{1 + sin θ}$$ = 4

(i) $$\frac{ cos θ}{csc θ + 1}$$ + $$\frac{ cos θ}{csc θ - 1}$$ = 2.

8. Solve: 2 sin A – 1 = 0. Hence, prove that sin (3A) = 3 sin A – 4 sin3 A.

9. If 2 cos θ - $$\sqrt{3}$$ = 0, find the value of θ.

Also, prove that sin (2θ) = 2 sin θ ∙ cos θ.

10. If 9 sin θ + 40 cos θ = 41, prove that 41 cos θ = 40.

11. If tan θ + sec θ = 3, where θ is acute then prove that 5 sin θ = 4.

Hint: tan θ + sec θ = 3

⟹ $$\frac{sin θ}{cos θ}$$ + $$\frac{1}{cos θ}$$ = 3

⟹ $$\frac{sin θ + 1}{cos θ}$$ = 3

⟹ sin θ + 1 = 3 cos θ

⟹ (sin θ + 1)2 = (3 cos θ)2

⟹ (sin θ + 1)2 = 9 cos2 θ

⟹ (sin θ + 1)2 = 9(1 - sin2 θ)

⟹ sin2 θ + 2 sin θ + 1 = 9 – 9 sin2 θ

⟹ 10 sin2 θ + 2 sin θ – 8 = 0

⟹ 5 sin2 θ + sin θ – 4 = 0

⟹ 5 sin2 θ + 5 sin θ - 4 sin θ – 4 = 0

⟹ 5 sin θ (sin θ + 1) - 4 (sin θ + 1) = 0

⟹ (sin θ + 1) (5 sin θ – 4) = 0

Answers on Worksheet on finding the unknown angle using trigonometric identities are given below to check the exact answers of the questions.

Answers

1. 60°

2. 30°

3. 30°

4. 60°

5. 60°

6. γ°, where tan  γ° = ½ or 2.

7. (i) No; 60°

(ii) No; 45°

8. 30°

9. 30°

10th Grade Math

From Worksheet on Finding the Unknown Angle Using Trigonometric Identities  to HOME PAGE

### New! Comments

Have your say about what you just read! Leave me a comment in the box below. Ask a Question or Answer a Question.

Didn't find what you were looking for? Or want to know more information about Math Only Math. Use this Google Search to find what you need.


text:
# Seemingly impossible constructive proofs

In the post Seemingly impossible functional programs, I wrote increasingly efficient Haskell programs to realize the mathematical statement

$\forall p : X \to 2. (\exists x:X.p(x)=0) \vee (\forall x:X.p(x)=1)$

for $X=2^\mathbb{N}$, the Cantor set of infinite binary sequences, where $2$ is the set of binary digits. Then in the post A Haskell monad for infinite search in finite time I looked at ways of systematically constructing such sets $X$ with corresponding Haskell realizers of the above omniscience principle.

In this post I give examples of infinite sets $X$ and corresponding constructive proofs of their omniscience that are intended to be valid in Bishop mathematics, and which I have formalized in Martin-Löf type theory in Agda notation. This rules out the example $X=2^\mathbb{N}$, as discussed below, but includes many interesting infinite examples. I also look at ways of constructing new omniscient sets from given ones. Such sets include, in particular, ordinals, for which we can find minimal witnesses if any witness exists.

Agda is a dependently typed functional programming language based on Martin-Löf type theory. By the Curry-Howard correspondence, Agda is also a language for formulating mathematical theorems (types) and writing down their proofs (programs). Agda acts as a thorough referee, only accepting correct theorems and proofs. Moreover, Agda can run your proofs. Here is a graph of the main Agda modules for this post, and here is a full graph with all modules.

## Some (counter)examples

### $X=\mathbb{N}$

The omniscience of $\mathbb{N}$ is not provable in constructive mathematics and comes under the fancy name LPO, or limited principle of omniscience. Its negation is not provable either, at least not in Bishop’s or Martin-Löf’s schools of constructive mathematics, and so we can’t say that LPO is false. Following Peter Aczel, we call such statements taboos. They are also known as Brouwerian counterexamples:

Taboo (LPO). $\quad\forall p : \mathbb{N} \to 2. (\exists x:\mathbb{N}.p(x)=0) \vee (\forall x:\mathbb{N}.p(x)=1)$.

### $X=\mathbb{N}_\infty$

However, if we enlarge the type of natural numbers with a point at infinity, we get a constructive proof of

Theorem. $\quad\forall p : \mathbb{N}_\infty \to 2. (\exists x:\mathbb{N}_\infty.p(x)=0) \vee (\forall x:\mathbb{N}_\infty.p(x)=1)$.

We remark that the proof doesn’t rely on continuity axioms, which are not available in Bishop’s and Martin-Löf’s approaches to constructive mathematics (see below).

How do we add a point at infinity to $\mathbb{N}$? We can’t simply take $\mathbb{N}_\infty = \mathbb{N} + 1$, because this is isomorphic to $\mathbb{N}$. The folklore way to add a limit point to $\mathbb{N}$ is to let $\mathbb{N}_\infty$ be the type of infinite, decreasing binary sequences. (There are other isomorphic possibilities, such as increasing sequences, or sequences with at most one $1$, among others.)

Such sequences represent finite and infinite counting processes of the form

$\underline{n} = 1^n 0^\omega$, $\quad\infty = 1^\omega$

($n$ ones followed by infinitely many zeros, and infinitely many ones respectively). This gives the extended natural numbers, also known as the generic convergent sequence or the one-point compactification of the natural numbers. The above encoding gives an embedding

$(n \mapsto \underline{n}) : \mathbb{N} \to \mathbb{N}_\infty$.

This shows that the reason why the omniscience of $\mathbb{N}$ fails is not simply that it is infinite, as the larger set $\mathbb{N}_\infty$ is omniscient.

Using this theorem, we can show that for every $p : \mathbb{N}_\infty \to 2$, the proposition $\forall n : \mathbb{N}.p(\underline{n})=1$ is decidable. The point is that now the quantification is over the natural numbers without violating (weak )LPO. In turn, using this, it follows that the non-continuity of a function $f : \mathbb{N}_\infty \to \mathbb{N}$ is decidable. It is also a corollary that the function type $\mathbb{N}_\infty \to \mathbb{N}$ has decidable equality.

The proof of the above theorem was presented at the Types’2011 meeting and is published in the Journal of Symbolic Logic (JSL), Volume 78, Number 3, September 2013, pages 764-784, under the title Infinite sets that satisfy the principle of omniscience in any variety of constructive mathematics. To save some work in the writing of this post, I offer the slides of the Types talk as an informal account of the original formal proof in Agda or the current one.

One (categorical) way of convincing ourselves that we have the right definition of $\mathbb{N}_\infty$ is to prove that it is the final coalgebra of the functor $1+(-)$.

### $X=2^\mathbb{N}$

The realizer given in Seemingly impossible functional programs relied on the hypothesis that all functions from the Cantor set $2^\mathbb{N}$ of infinite binary sequences to the two-point set $2$ are uniformly continuous.

This statement fails, or rather is independent, in Bishop mathematics or Martin-Löf‘s type theory: it can’t be proved or disproved. In Brouwer‘s intuitionism, the statement holds, but it is false in Markov’s Russian school of constructive mathematics, and so it is in classical mathematics, because discontinuous functions can be easily defined by case analysis using excluded middle. Bishop mathematics is by design intended to be compatible with both classical mathematics and all varieties of constructive mathematics, in the sense that any theorem in Bishop mathematics is a theorem of classical mathematics and its constructive varieties. Martin-Löf’s type theory is a formal system intended to be capable of formalizing Bishop mathematics and run it on computers.

However, although Agda is based on Martin-Löf type theory, and hence the above remarks apply, we can disable the termination checker in a particular module to prove a countable Tychonoff Theorem for inhabited omniscient sets, which gives the omniscience of $X=2^\mathbb{N}$. This is the only place in our development that we commit such a sin, relying on an external termination proof. But notice that, although this goes beyond the realms of Bishop and Martin-Löf mathematics, the result is still compatible with classical mathematics, as all sets are omniscient in classical mathematics, by virtue of the principle of excluded middle.

(At this point I should disclose that when I say set I mean type. Apologies to HoTT people, for whom (h)sets are particular kinds of types.)

## Searchable sets

I formulated the above in terms of the notion of omniscience because it is perhaps more familiar. But, for many purposes, including showing the omniscience of $\mathbb{N}_\infty$, it is more convenient to work with the notion of searchable set. We say that $X$ is searchable if

$\forall p:X \to 2.\exists x_0 : X. p(x_0)=1 \to \forall x:X.p(x)=1$.

This is the Drinker Paradox, which says that in every (inhabited) pub $X$ there is a person $x_0$ such that if $x_0$ drinks then everybody drinks, where $p(x)=1$ means that $x$ drinks. Thus, a pub $X$ is searchable iff it satisfies the Drinker Paradox for every $2$-valued notion $p$ of “drinking”.

It is immediate that any searchable set is inhabited. To get the omniscience of $X$ from its searchability, given $p$ we first find a “universal witness” $x_0$ by the searchability of $X$. We can then check whether $p(x_0)=0$ or $p(x_0)=1$ by the decidability of equality of the set $2$. In the first case we conclude $\exists x:X.p(x)=0$ directly, and the second case gives $\forall x:X.p(x)=1$ by the definition of searchability, and so $X$ is indeed omniscient. Conversely, if we know an inhabitant $a : X$ and that $\exists x:X.p(x)=0$ or $\forall x:X.p(x)=1$, in the first case we let $x_0=x$ and in the second case we let $x=a$ to conclude that $X$ is searchable. This shows that a set is searchable iff it is both inhabited and omniscient.

## Constructing new searchable sets from old

We have already mentioned the countable Tychonoff Theorem, but this is a rogue example, as it departs from the constructive foundations we are interested in in this post.

### Sums

If we have a searchable set $X$ and a family $(Y_x)_{x : X}$ of searchable sets, then its sum or disjoint union

$\sum_{x : X} Y_x$

is also searchable. This follows directly the ideas discussed in the paper with Paulo Oliva published in Mathematical Structures in Computer Science, Volume 20, Issue 2, April 2010, Cambridge University Press.

Two particular cases of interest are

1. (binary Tychonoff) If $X$ and $Y$ are searchable then so is $X \times Y$ (when $Y$ doesn’t depend on $X$), and
2. If $Y_0$ and $Y_1$ are searchable then so is $Y_0 + Y_1$ (when $X=2$).

The rogue proof of the countable Tychonoff Theorem mentioned above recursively iterates the binary Tychonoff Theorem, as in the above paper with Paulo.

### Squashed sums

The mysterious terminology comes from the above JSL paper, where this is a construction that really does perform some squashing (in a metric sense) within the Cantor space $2^\mathbb{N}$. Here we give a generalization of the construction that makes sense for sets that are not necessarily embedded in the Cantor space (unpublished, but done in 2011 and implemented in Agda in 2012).

Given countably many sets $X_n$, we want to construct its disjoint sum with a limit point at infinity, very much like we added a point at infinity to the natural numbers. We do this in two steps. We first extend the family $X : \mathbb{N} \to U$, where $U$ is the universe of types, to a family $Y : \mathbb{N}_\infty \to U$ as follows:

$Y_i = \prod_{n : \mathbb{N}} X_n^{i = \underline{n}}$.

Here $=$ is the identity type and we used exponential notation for the function space $i = \underline{n} \to X_n$.
The idea is that this product has at most one non-trivial factor, so that we get

$Y_{\underline{n}} \cong X_n$, $\quad Y_{\infty} \cong 1$

where $1$ is the one-point set. In the second step, we take the ordinary sum of the family $Y$. So, in summary, we define the squashed sum of the family $X$ to be

$\sum^1 X = \sum_{i : \mathbb{N}_\infty} \prod_{n : \mathbb{N}} X_n^{i = \underline{n}}$.

The theorem is that if $X_n$ is searchable for every $n:\mathbb{N}$ then the squashed sum $\sum^1 X$ is also searchable. The subtlety is to prove that $Y_i$ is searchable for every $i : \mathbb{N}_\infty$ without performing the taboo case analysis $i=\underline{n}$ or $i = \infty$, as this amounts to LPO. This subtlety amounts a provable, curious instance of the Tychonoff Theorem.

### The world’s smallest Tychonoff Theorem for searchable sets

If $X$ has at most one point (any two of its points are equal), or, in HoTT terminology, $X$ is an hproposition or a $-1$-truncated type, and $Y : X \to U$ is a family of searchable sets, then

$\prod_{x : X} Y_x$

is also searchable. In other words, searchable sets are closed under the formation of products with at most one factor. This is clear with excluded middle, but the point is that it is not needed.

### Injectivity of the universe and further generalized squashed sums

The above extension of $X : \mathbb{N} \to U$ to $Y:\mathbb{N}_\infty \to U$ is an instance of a more general phenomenon. If $A$ and $X : A \to U$ are arbitrary, and $j : A \to B$ is an embedding, then $X$ extends to a family $X / j : B \to U$ along $j$.
For this we need the right definition of embedding, namely that each fiber

$j^{-1}(b) = \sum_{a : A} b = j(a)$

is an hproposition. Then $X / j$ is constructed as

$(X / j)(b) = \prod_{(a , r) : j^{-1}(b)} X_a \cong \prod_{a : A} X_a^{b = j(a)}$.

We then have that if $X$ is a family of searchable sets, so is $X / j$, using the hproposition-indexed Tychonoff Theorem, and that the extended sum $\sum(X / j)$ is searchable if $B$ is searchable, even if $A$ isn’t searchable, using the fact that sums preserve searchability.

## Final remarks

### A brief word about searchable ordinals

If $X_n$ is a family of ordinals in the sense of the HoTT book, then so is its squashed sum, under the lexicographic order with the added point at infinity as the largest element. I haven’t proved this in Agda yet (it is in my to do list). But I have proved in Agda some preliminary facts towards this. What needs to be done is to add order to this. Some preliminary Agda modules toward that have been developed.

### Function extensionality: a second sin?

To avoid setoids (what Bishop actually calls sets) I have invoked the axiom of function extensionality (any two pointwise equal functions are equal). This will be available in the next generation of proof assistants / programming languages based on HoTT which are under active development in various research centers. However, for the moment, it turns out that for the majority of theorems, we can get away with the double negation of function extensionality, which can be postulated without loss of computational content. Chuangjie Xu has formally checked that doubly negated function extensionality is enough for a few of the theorems discussed above, starting from the crucial one that $\mathbb{N}_\infty$ is searchable. What one observes in practice in my implementation, which uses (positive) function extensionality, is that when one runs examples one gets numerical results that don’t get stuck in irreducible terms containing the function extensionality constant funext.

### Informal proofs

I plan to write a paper with the informalization of the Agda development (other than that already provided in the JSL paper mentioned above). For the moment, this blog post is a first approximation, with an informal discussion of some the results proved in the Agda development.


text:
×
Get Full Access to Chemistry: The Central Science - 12 Edition - Chapter 5 - Problem 27e
Get Full Access to Chemistry: The Central Science - 12 Edition - Chapter 5 - Problem 27e

×

# Calculate and determine whether the process is endothermic

ISBN: 9780321696724 27

## Solution for problem 27E Chapter 5

Chemistry: The Central Science | 12th Edition

• Textbook Solutions
• 2901 Step-by-step solutions solved by professors and subject experts
• Get 24/7 help from StudySoup virtual teaching assistants

Chemistry: The Central Science | 12th Edition

4 5 1 239 Reviews
22
5
Problem 27E

Calculate $$\Delta E$$ and determine whether the process is endothermic or exothermic for the following cases: (a) $$q=0.763 \ kJ$$ and $$w=-840 \ J$$; (b) a system releases $$66.1 \ kJ$$ of heat to its surroundings while the surroundings do $$44.0 \ kJ$$ of work on the system; (c) the system absorbs $$7.25 \ kJ$$ of heat from the surroundings while its volume remains constant (assume that only $$P-V$$ work can be done).

Equation Transcription:

Text Transcription:

Delta E

q = 0.763 kJ

w = -840 J

66.1 kJ

44.0 kJ

7.25 kJ

P-V

Step-by-Step Solution:
Step 1 of 3

Heart: ● Overview of the Cardiovascular System ○ The heart propels blood to and from most body tissues via two basic types of blood vessels calle rteries and veins. ○ Arteries are blood vessels that carry   way to the heart. ○ Veins are blood vessels that carry  d ack to the heart. ○ The arteries and veins entering and leaving the heart are called great vessels. ● General Characteristics and Functions of the Heart ○ Blood flow through the heart is unidirectional because of four heart valves. ○ The heart is functionally two side-by-side pumps that work at the same rate and pump the same volume of blood. ■ One pump directs blood to the lungs. ■ One pump directs blood to most body tissues. ○ The heart generates lood pressure through alternate cycles of the heart wall’s contraction and relaxation. ○ Blood pressure is the force of the blood pushing against the inside walls of blood vessels. ○ A minimum blood pressure is essential to circulate blood throughout the body. ● Pulmonary and Systemic Circulations ○ The cardiovascular system consists of two circulations: ■ Pulmonary- r ight side of the heart and the pulmonary arteries and veins; right ventricle blood is conveyed to the lungs and back to the left atrium of the heart ■ Systemic- from the left ventricle

Step 2 of 3

Step 3 of 3

## Discover and learn what students are asking

#### Related chapters

Unlock Textbook Solution


text:
## Engage NY Eureka Math 8th Grade Module 7 Lesson 2 Answer Key

### Eureka Math Grade 8 Module 7 Lesson 2 Exercise Answer Key

Exercise 1.
Determine the positive square root of 81, if it exists. Explain.
The square root of 81 is 9 because 92=81.

Exercise 2.
Determine the positive square root of 225, if it exists. Explain.
The square root of 225 is 15 because 152=225.

Exercise 3.
Determine the positive square root of -36, if it exists. Explain.
The number -36 does not have a square root because there is no number squared that can produce a negative number.

Exercise 4.
Determine the positive square root of 49, if it exists. Explain.
The square root of 49 is 7 because 72=49.

Discussion

Place the numbers $$\sqrt{1}$$, $$\sqrt{4}$$, $$\sqrt{9}$$, and $$\sqrt{1}$$6 on the number line, and explain how you knew where to place them.
Solutions are shown below in red.

Place the numbers $$\sqrt{2}$$ and $$\sqrt{3}$$ on the number line. Be prepared to explain your reasoning.
Solutions are shown below in red. Students should reason that the numbers $$\sqrt{2}$$ and $$\sqrt{3}$$ belong on the number line between $$\sqrt{1}$$ and $$\sqrt{4}$$. They might be more specific and suggest that the numbers $$\sqrt{2}$$ and $$\sqrt{3}$$ sit equally spaced in the interval between 1 and 2. This idea suggests that 1 $$\frac{1}{3}$$ might be a good approximation for $$\sqrt{2}$$ and 1 $$\frac{2}{3}$$ for $$\sqrt{3}$$. Of course, this suggested spacing is just speculation for now.

Place the numbers $$\sqrt{5}$$, $$\sqrt{6}$$, $$\sqrt{7}$$, and $$\sqrt{8}$$ on the number line. Be prepared to explain your reasoning.
Solutions are shown below in red. The discussion about placement should be similar to the previous one.

Place the numbers $$\sqrt{1}$$0, $$\sqrt{1}$$1, $$\sqrt{1}$$2, $$\sqrt{1}$$3, $$\sqrt{1}$$4, and $$\sqrt{1}$$5 on the number line. Be prepared to explain your reasoning.
Solutions are shown below in red. The discussion about placement should be similar to the previous one.

Our work on the number line shows that there are many more square roots of whole numbers that are not perfect squares than those that are perfect squares. On the number line above, we have four perfect square numbers and twelve that are not! After we do some more work with roots, in general, we will cover exactly how to describe these numbers and how to approximate their values with greater precision. For now, we will estimate their locations on the number line using what we know about perfect squares.

Determine the positive square root of the number given. If the number is not a perfect square, determine which whole number the square root would be closest to, and then use guess and check to give an approximate answer to one or two decimal places.
Exercise 5.
$$\sqrt{49}$$
7

Exercise 6.
$$\sqrt{62}$$
The square root of 62 is close to 8. The square root of 62 is approximately 7.9 because 7.92=62.41.

Exercise 7.
$$\sqrt{122}$$
The square root of 122 is close to 11. Students may guess a number between 11 and 11.1 because 11.052=122.1025.

Exercise 8.
$$\sqrt{400}$$
20

Exercise 9.
Which of the numbers in Exercises 5–8 are not perfect squares? Explain.
The numbers 62 and 122 are not perfect squares because there is no integer x to satisfy x2=62 or x2=122.

### Eureka Math Grade 8 Module 7 Lesson 2 Problem Set Answer Key

Determine the positive square root of the number given. If the number is not a perfect square, determine the integer to which the square root would be closest.
Question 1.
$$\sqrt{169}$$
13

Question 2.
$$\sqrt{256}$$
16

Question 3.
$$\sqrt{81}$$
9

Question 4.
$$\sqrt{147}$$
The number 147 is not a perfect square. It is between the perfect squares 144 and 169 but closer to 144. Therefore, the square root of 147 is close to 12.

Question 5.
$$\sqrt{8}$$
The number 8 is not a perfect square. It is between the perfect squares 4 and 9 but closer to 9. Therefore, the square root of 8 is close to 3.

Question 6.
Which of the numbers in Problems 1–5 are not perfect squares? Explain.
The numbers 147 and 8 are not perfect squares because there is no integer x so that x2=147 or x2=8.

Question 7.
Place the following list of numbers in their approximate locations on a number line.
$$\sqrt{32}$$, $$\sqrt{12}$$, $$\sqrt{27}$$, $$\sqrt{18}$$, $$\sqrt{23}$$, and $$\sqrt{50}$$

Question 8.
Between which two integers will $$\sqrt{45}$$ be located? Explain how you know.
The number 45 is not a perfect square. It is between the perfect squares 36 and 49 but closer to 49. Therefore, the square root of 45 is between the integers 6 and 7 because $$\sqrt{36}$$ = 6 and $$\sqrt{49}$$ = 7 and $$\sqrt{36}$$ < $$\sqrt{45}$$ < $$\sqrt{49}$$.

### Eureka Math Grade 8 Module 7 Lesson 2 Exit Ticket Answer Key

Question 1.
Write the positive square root of a number x in symbolic notation.
$$\sqrt{x}$$

Question 2.
Determine the positive square root of 196. Explain.
$$\sqrt{196}$$ = 14 because 142 = 196.

Question 3.
The positive square root of 50 is not an integer. Which whole number does the value of $$\sqrt{50}$$ lie closest to? Explain.
$$\sqrt{50}$$ is between 7 and 8 but closer to 7. The reason is that 72=49, and 82=64. The number 50 is between 49 and 64 but closer to 49. Therefore, the square root of 50 is close to 7.
Place the following numbers on the number line in approximately the correct positions: $$\sqrt{16}$$, $$\sqrt{9}$$, $$\sqrt{11}$$, and 3.5.


text:
# Isometric imbedding of a sphere with positively curved metric

QUESTION. Given a Riemannian metric on the sphere $S^n$ with positive sectional survature. Can it be isometrically imbedded into $\mathbb{R}^{n+1}$ (of any class of regularity) as a boundary of a convex set?

This question was motivated by the following three well known facts on isometric imbeddings (please correct me if references are not precise).

1) Given a smooth Riemannian metric with strictly positive Gauss curvature on the 2-sphere $S^2$, it can be isometrically imbedded into $\mathbb{R}^3$ such that its image bounds a convex set (Nirenberg, Pogorelov).

2) On $S^n$ with $n>2$ there exist smooth Riemannian metrics (even with positive sectional curvature) which cannot be smoothly (!) imbedded into $\mathbb{R}^{n+1}$. (Common knowledge.)

3) Any Riemannian metric on $S^n$ can be $C^1$-regularly isometrically imbedded into $\mathbb{R}^{n+1}$. (Special case of Nash's theorem.)

Igor is essentially right. If $n > 2$ and the embedding is convex, then the second fundamental form exists almost everywhere. Using the Gauss equations per Robert's answer, it extends uniquely and smoothly to everywhere. The rest is straightforward. I'm omitting it because I'm typing this on an iPhone.

The $C^1$ but non-convex case is due to Nash (who did it in codimension 2) and Kuiper (who did it in codimension 1). It is not a special case of smooth Nash embedding theorem.

ADDED: The argument can be made rigorous by taking a family of smooth convex hypersurfaces converging uniformly to the original convex hypersurface and using the inverse to the map from positive definite second fundamental forms to curvature tenors defined by the Gauss equations to show that the second fundamental form has to converge uniformly to a continuos limit that also weakly solves the Codazzi equations. This can then be integrated to show that the embedding is in fact smooth. Uniqueness then follows by the Cohn-Vossen theorem.

• Did you actually claim that every convex isometric imbedding of a smooth metric on the sphere with positive sectional curvature is infinitely smooth? In that case the answer to my question would be negative. – MKO Sep 21 '15 at 8:41
• Yes, that's right. – Deane Yang Sep 21 '15 at 10:40
• I don't see how to make this a rigorous argument. You are assuming that one can use Gauss equations to compute the curvature tensor of a metric which a priori at best is just $C^1$. That is far from obvious. In fact, you can't even assume it's $C^1$. – Vitali Kapovitch Sep 21 '15 at 12:45
• Yes, I should add details. Some PDE regularity theory is needed – Deane Yang Sep 21 '15 at 13:20

In the smooth category, the problem has a completely different character for $n>2$ than when $n=2$.

The first obstruction is whether there exists a positive definite quadratic form~$h$ on $S^n$ that satisfies the Gauss equation $h\circledast h = \mathrm{Riem}(g)$ (where $\circledast$ denotes the so-called Kulkarni product $\circledast:S^2(S^2T^*)\to S^2(\Lambda^2T^*)$). When $n=3$, such an $h$ always exists (and is unique) when $\mathrm{Riem}(g)$ has positive sectional curvature. When $n>3$, this places algebraic conditions on $\mathrm{Riem}(g)$; when $\mathrm{Riem}(g)$ has positive sectional curvature and a positive definite $h$ exists satisfying the Gauss equation, it is unique.

The second condition is that the $h$ that is found satisfying the Gauss equation must also satisfy the Codazzi equation $\delta_g h = 0$.

These conditions are sufficient.

• Isn't this only relevant when the embedding is smooth also (so, relevant to the OP's (2))? His question really seems to be: if a metric does NOT admit a $C^2$ embedding, can an embedding bound a convex set (my guess would be no, since a boundary of a convex set is very close to $C^2$ anyhow, and having the induced metric be $C^2$ would presumably guarantee that the embedding is $C^2$ also - I am not sure enough to make this an answer). – Igor Rivin Sep 20 '15 at 15:22
• I didn't gather that that was the question, but OK. As far as I know, the best results on optimal regularity for isometric embeddings in low codimension can be read about in Camillo De Lellis' 2015 Abel Prize lecture: math.uzh.ch/fileadmin/user/delellis/publikation/iso60.pdf – Robert Bryant Sep 20 '15 at 17:25
• That is an interesting reference, but (and I admit I only scanned it), I assume that much stronger regularity results are available in the convex case. Apologies if this is addressed in the paper... – Igor Rivin Sep 20 '15 at 17:38