text:
# Tag Archives: Higher order digital net

## Digital Nets and Sequences Preprint

A complete preprint of the book

is now available here. The final published version can be obtained directly from Cambridge University Press here.

The preprint version differs of course from the final version, for instance, the page numbers are different. However, the numbering of Chapters, Sections, Theorems, Lemmas, Corollaries, Definitions and Examples is the same in both versions. The list of corrections is for the published version. We do not have a separate list for the preprint version (though the corrections for the published version also apply to the preprint version).

## Higher order nets and a higher order Sudoku

In the following we first describe a connection of $(t,m,s)$-nets and Sudoku and then generalize the Sudoku in analogy to higher order $(t,\alpha, \beta, m, n, s)$-nets in base 3. A new type of Sudoku puzzle is presented at the end. Continue reading

## Some possible simplifications of the notation of higher order nets and sequences

In this entry I discuss the definition of (digital) higher order nets and sequences and some possible simplifications of the notation.

Digital higher order nets and sequences have been introduced in

whereas higher order nets have been introduced in

• [2] J. Dick and J. Baldeaux, Equidistribution properties of generalized nets and sequences. In: Proceedings of the MCQMC’08 conference, Montreal, Canada, P. L’Ecuyer and A. Owen (eds.), pp. 305–323, 2009. doi: 10.1007/978-3-642-04107-5_19 An earlier version can be found here.

There are several parameters occurring in the definition of higher order nets, namely $t, \alpha,\beta, n, m, s, b$ and for higher order sequences we have the parameters $t, \alpha, \beta, \sigma, s, b.$

(Digital) higher order nets and sequences are point sets $\{\boldsymbol{x}_0,\ldots, \boldsymbol{x}_{b^m-1}\} \subset [0,1)^s$ and sequences $\{\boldsymbol{x}_0,\boldsymbol{x}_1, \ldots, \}$ such that

$\displaystyle \left|\int_{[0,1]^s} f(\boldsymbol{x}) \,\mathrm{d} \boldsymbol{x} - \frac{1}{N} \sum_{n=0}^{N-1} f(\boldsymbol{x}_n) \right| = \mathcal{O} (N^{-\alpha} (\log N)^{\alpha s}),$

where ${}N =b^m$ is the number of quadrature points and ${} \alpha$ is the smoothness of the integrand ${}f.$ Continue reading

## Higher order scrambling

This paper deals with a generalization of Owen’s scrambling algorithm which improves on the convergence rate of the root mean square error for smooth integrands. The bound on the root mean square error is best possible (apart from the power of the $\log N$ factor) and this can also be observed from some simple numerical examples shown in the paper (note that the figures in the paper show the standard deviation (or root mean square error) and not the variance of the estimator). In this post you can also find Matlab programs which generate the quadrature points introduced in this paper and a program to generate the numerical results shown in the paper. Continue reading

## How to generate higher order Sobol points in Matlab and some numerical examples

Higher order digital nets and sequences are quasi-Monte Carlo point sets $\{\boldsymbol{x}_{n-1}\}_{n=1}^N,$ where $N=b^m$ for digital nets and $N=\infty$ for digital sequences (for more background information on this topic see Chapters 1-4 and Chapter 8 in the book; several sample chapters of this book can be downloaded here), which satisfy the following property:

$\displaystyle \left|\int_{[0,1]^s} f(\boldsymbol{x}) \, \mathrm{d} \boldsymbol{x} - \frac{1}{b^m} \sum_{n=0}^{b^m-1} f(\boldsymbol{x}_n) \right| \le C_{s,\alpha} \frac{(\log N)^{s \alpha}}{N^\alpha}, \hspace{2cm} (1)$

where $\alpha \ge 1$ is the smoothness of the integrand ${}f$ and $C_{s,\alpha} \textgreater 0$ is a constant which only depends on ${}s$ and ${}\alpha$ (but not on ${}N).$ For instance, if ${}f$ has square integrable partial mixed derivatives up to order ${}2$ in each variable, then we get a convergence rate of $\mathcal{O}(N^{-2+\varepsilon}),$ where ${}N$ is the number of quadrature points used in the approximation and $\varepsilon >0$ can be chosen arbitrarily small. If ${}f$ has ${}3$ derivatives then we get a convergence of $\mathcal{O}(N^{-3+\varepsilon}),$ and so on.

This method has been introduced in the papers:

The first paper only deals with periodic functions, whereas the second paper also includes nonperiodic functions.

For some heuristic explanation how higher order digital nets and sequences work see the paper:

• J. Dick, On quasi-Monte Carlo rules achieving higher order convergence. In: Proceedings of the MCQMC’08 conference, Montreal, Canada, P. L’Ecuyer and A. Owen (eds.), pp. 73–96, 2009. doi: 10.1007/978-3-642-04107-5_5 An earlier version can be found here.

In this entry we provide a Matlab program which generates point sets which satisfy the property (1). Continue reading

## Construction Algorithms for Higher Order Polynomial Lattice Rules

We recently submitted the manuscript

This paper fits into the work on higher order quasi-Monte Carlo rules which started with [22] and [31]. It can be viewed as the higher order extension of [7], where classical polynomial lattice rules were considered.

1. Construction Algorithms

As stated in the title of the manuscript, we present construction algorithms for higher order polynomial lattice rules. The construction is based on the worst-case error rather than the quality parameter ${t}$. This allows us to find good higher order polynomial lattice rules for weighted function spaces. It also presents a feasible alternative to the direct construction introduced in [31] (and [22] for the periodic case).

We use a variety of approaches to achieve our results. Continue reading

## Duality Theory and Propagation Rules for Higher Order Nets

We (J. Baldeaux, J.D., F. Pillichshammer) just submitted a manuscript on Duality Theory and Propagation Rules for Higher Order Nets (you can download the manuscript by clicking on the title). In a nutshell, propagation rules are methods to construct, from given nets with some given parameters, new nets with at least one parameter different from the given nets. Duality theory on the other hand is the vehicle which allows us to analyse those propagation rules. It is an analytic description (using Walsh functions in our case) of the geometric properties of nets.

The manuscript is a continuation of the paper with P. Kritzer on Duality Theory and Propagation Rules for Generalized Digital Nets [44]. (Note that in some papers the notion generalized (digital) net’ was used instead of the term (digital) higher order net’.) The difference is that we do not assume that the point sets are constructed by the digital construction scheme.

Most propagation rules for classical ${(t,m,s)}$-nets have a higher order analogue. This applies to digital as well as geometric nets. Additionally there are also some further propagation rules which do not exist for classical nets (for example the higher order to higher order construction). The higher order to higher order propagation rule is, as of now, still the only method to obtain higher order nets from classical nets. Fortunately it works in the digital as well as geometric case.

1. A subnet propagation rule for digital higher order nets

We give an example of a propagation rule in the following. In the classical case there is a propagation rule which states that: Continue reading


text:
Jupyter Notebook

# Exercice 1. Automatic detection of speaker’s intention from supra-segmental features

In this exercice, we consider a Human-Robot Interaction situation in which a human is evaluating actions performed by the Kismet robot: by showing approval or expressing prohibition. The initial corpus contains a total of 1002 American English utterances of varying linguistic content produced by three female speakers in three classes of affective communicative intents (aproval, attention, prohibition (weak)). The affective intents sound acted and are expressed rather strongly. The speech recordings are of variable length, mostly in the range of 1.8 - 3.25s. We extracted prosodic features such as the fundamental frequency (denoted by $f_0$ from now on) and energy. Files are respectively named *.f0 and *.en (and contain time, value entries on each line).

The aim of this exercice is to develop a human feedback classifier: positive (approval)/negative (prohibition). This classifier might be used to teach the robots and/or to guide the robot’s learning.

Development of the human feedback classifier:

1. Extraction of prosodic features (f0 and energy)
2. Extraction of functionals (statistics) that will be our features in the supervised learning task: mean, maximum, range, variance, median, first quartile, third quartile, mean absolute of local derivate
3. Check functionals for both voiced (i.e. $f_0 ≠ 0$) and unvoiced segments, and then determine which segments are suited for the approach.
4. Build two databases by randomly extracting examples: a learning database (60% of the data points) and a test one
5. Train a classifer ($k$-nearest neighbors (k-NN) algorithm))
6. Discuss the performance of the classifier

## 1. Extraction of prosodic features ($f_0$ and $energy$)

We found that, in the given data, the file names are contain either at, pw or ap, which are likely to represent the intention classes “Attention”, “Prohibition Weak” and “Approval” respectively.

Since the aim of this exercice is to develop a human feedback classifier for positive (“Approval”) / negative (“Prohibition”) intentions, we extract the files labelled as pw and ap and exclude the files labelled as at.

For our project, we cooperated online using Google Colab. The codes for extracting the files labelled as pw and ap and their the prosodic features is shown below:

import urllib.request
import numpy as np
import pandas as pd
import itertools
import matplotlib.pyplot as plt
import ggplot

def list_from_URL(file_URL, function_applied=None):
lines = []

for line in lines_bytes:
line = line.decode("utf-8").rstrip()

if function_applied is not None:
line = function_applied(line)

lines.append(line)

return lines

filenames = list(set(filenames))

files = []
indices = []

for file in filenames:

file_dicts = [{key:val for key, val in zip(['time', 'f0'], map(float, l.split()))} for l in list_from_URL(URL_f0)]

for l, d in zip(list_from_URL(URL_en), file_dicts):
d["file"] = file
d["en"] = float(l.split()[1])
d["label"] = file[-2:]

files.extend(file_dicts)

# How files looks like:
# # files = [
# #           {"file": "cy0001at", "time": 0.02, "f0": 0., "en": 0.},
# #           {"file": "cy0001at", "time": 1.28, "f0": 0., "en": 0.},
# #           ...
# #           {"file": "li1450at", "time": 0.02, "f0": 0., "en": 0.},
# #           {"file": "li1450at", "time": 1.56, "f0": 404., "en": 65.}
# #         ]

pd.DataFrame(files).to_csv('data.csv', encoding='utf-8', index=False) # To reuse it next time

# loading training data, once it has been saved on the repository
df1 = df.loc[df['label'] != 'at']

## 2. Extraction of functionals (statistics) : mean, maximum, range, variance, median, first quartile, third quartile, mean absolute of local derivate

We calculated the mean, max, range, variance, median. first quartile, third quartile and mean absolute of local derivate for each en and f0 file. Using a pandas DataFrame, the code to extract these functionals is the following:

list_features  = ['mean',
'max',
('range', lambda x: max(x)-min(x)),
'var',
'median',
('1st_quantile', lambda x: x.quantile(.25)),
('3rd_quantile', lambda x: x.quantile(.75)),
('mean_absolute_local_derivate', lambda x: abs(x.diff()).mean())
]

Table $1$ and Table $2$ show the first five lines of the statistics functionals of f0 and en files respectively:

#### Table $1$: Statistics of f0 files (first $5$ lines)

file mean max range var median 1st_quantile 3rd_quantile mean_absolute_local_derivate
cy0007pw 92.3 257.0 257.0 10372.5 0.0 0.0 189.5 13.7
cy0008pw 78.4 250.0 250.0 9930.1 0.0 0.0 192.0 26.4
cy0009pw 69.1 243.0 243.0 8927.2 0.0 0.0 182.3 12.9
cy0010pw 29.2 221.0 221.0 4696.2 0.0 0.0 0.0 15.27
cy0011pw 110.7 230.0 230.0 9290.4 172.0 0.0 192.5 7.5

#### Table $2$: Statistics of en files (first $5$ lines)

file mean max range var median 1st_quantile 3rd_quantile mean_absolute_local_derivate
cy0007pw 52.3 71.0 71.0 228.5 52.0 41.0 66.0 2.9
cy0008pw 47.7 70.0 70.0 321.9 43.0 41.0 64.5 3.9
cy0009pw 49.5 74.0 74.0 260.8 42.0 40.8 66.0 3.5
cy0010pw 46.1 77.0 77.0 165.8 42.0 41.0 50.8 3.3
cy0011pw 53.7 71.0 71.0 258.1 62.0 41.3 66.0 2.3

## 3. Check functionals for both voiced (i.e. $f_0$ ≠ $0$) and unvoiced segments. Which segments are suited for the approach?

We extract voiced segments by only keeping the data whose $f_0$ value is not equal to $0$. The code for extracting voiced sections and calculating the statistics of them is:

voiced = df1.loc[df1['f0']!=0].groupby('file')['f0','en'].agg(list_features)
voiced.head() # to visualize the first rows of the dataframe

Similarly, we extract the unvoiced segments by looking for the data whose $f_0$ value equals $0$. The code is:

unvoiced = df1.loc[df1['f0']==0].groupby('file')['en'].agg(list_features)

The first $5$ lines of statistics for voiced segments in f0 and en files are shown in Table $3$ and Table $4$ respectively:

#### Table $3$: Statistics of f0 files of voiced segments (first $5$ lines)

file mean max range var median 1st_quantile 3rd_quantile mean_absolute_local_derivate
cy0007pw 200.3 257.0 90.0 675.9 191.0 182.5 213.0 5.9
cy0008pw 200.0 250.0 83.0 538.4 198.5 179.5 210.0 10.4
cy0009pw 194.4 243.0 77.0 446.9 190.0 180.0 209.0 7.2
cy0010pw 186.1 221.0 67.0 465.3 178.5 171.3 204.3 6.5
cy0011pw 191.9 230.0 66.0 314.8 190.0 179.0 204.0 4.1

#### Table $4$: Statistics of en files of voiced segments (first $5$ lines)

file mean max range var median 1st_quantile 3rd_quantile mean_absolute_local_derivate
cy0007pw 65.9 71.0 16.0 17.8 66.0 63.5 70.0 1.7
cy0008pw 61.0 70.0 70.0 242.7 66.0 61.5 68.0 5.8
cy0009pw 67.3 74.0 20.0 17.9 68.0 66.0 70.0 2.9
cy0010pw 65.8 77.0 25.0 50.5 64.0 62.0 70.8 4.0
cy0011pw 65.3 71.0 19.0 14.7 65.0 63.0 68.0 0.9

The first $5$ lines of statistics of unvoiced segments for en files are shown in Table $5$:

#### Table $5$: Statistics of en files of unvoiced segments (first $5$ lines)

file mean max range var median 1st_quantile 3rd_quantile mean_absolute_local_derivate
cy0007pw 40.7 58.0 58.0 113.6 41.0 40.5 43.5 3.7
cy0008pw 39.2 58.0 58.0 189.6 42.0 41.0 43.0 5.2
cy0009pw 39.6 56.0 56.0 119.6 41.0 40.0 42.0 3.6
cy0010pw 42.4 68.0 68.0 101.4 41.0 40.0 43.0 3.1
cy0011pw 37.8 51.0 51.0 150.9 41.0 40.0 42.0 4.1

To judge which segments are better for the approach, we should check how separable (with respect to the label ap or pw) the data is in each situation. We first look at the overall statistics of the two segments for the two classes “Approval” and “Prohibition Weak”. The results are shown in Table $6$:

#### Table $6$: Statistics of “Approval” (ap) and “Prohibition Weak” (pw) files for voiced and unvoiced segments

segments file class mean max range var median 1st_quantile 3rd_quantile mean_absolute_local_derivate
voiced f0 ap 289.5 597.0 521.0 11013.0 272.0 199.0 370.5 24.9
voiced f0 pw 192.4 597.0 522.0 2702.1 191.0 170.0 218.0 14.4
voiced en ap 73.3 93.0 93.0 88.2 74.0 68.0 79.0 3.5
voiced en pw 71.6 91.0 91.0 84.7 72.0 65.0 79.0 3.0
unvoiced f0 ap 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
unvoiced f0 pw 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
unvoiced en ap 46.4 94.0 94.0 239.2 43.0 41.0 55.0 3.9
unvoiced en pw 47.6 91.0 91.0 231.1 47.0 40.0 58.0 3.5

Table $6$ shows that, in voiced segments, the statistics of $f_0$ seem different for ap and pw files:

• the en functionals of voiced and unvoiced segments seem very close to one another between the two types of classes (ap and pw)
• and of course, the statistics of f0 files for unvoiced segments are all $0$.

Thus, so far from the results of Table 6, $f_0$ values of voiced segments seem a better measurement for the approach.

This intuition is backed up by what we do next: by plotting the mean absolute local of derivate as a function of the variance for each type (voiced and unvoiced) of segments, we see that the data points seem more separable (based on their class) in the voiced case than in the unvoiced one:

Figure 1 suggests that the approval and prohibition classes can be reasonably well separated using their $f_0$ variance and mean absolute local derivate for voiced segments, supporting our previous idea voiced segments can be a good measurement for classifying.

However, by doing the same for unvoiced segments, we see that the data is not as easily separable:

Figure 2 shows that the data points cannot be separated well with respect to their classes using the variance and mean absolute local derivate of energy for unvoiced segments.

So on the whole, by plotting our randomly selected data, we found that voiced segments seem better suited for the classification task at hand.

## 4. Build two databases by randomly extracting examples : Learning database ($60$%) and Test database

We randomly extract $60$% data from the original dataset to build the training set and the remaining data was used as the test set. The code for this procedure is provided below:

def train_test(df=df1, train_percentage=.6, seed=1):

voiced = df.loc[df['f0']!=0].groupby('file')['f0','en'].agg(list_features)
unvoiced = df.loc[df['f0']==0].groupby('file')['en'].agg(list_features)

X, Y = {}, {}

X['voiced'], Y['voiced'] = {}, {}
X['unvoiced'], Y['unvoiced'] = {}, {}

X['voiced']['all'] = np.array(df.groupby('file')['f0','en'].agg(list_features))
Y['voiced']['all'] = np.array(df.loc[df['f0']!=0].groupby(['file']).min().label.values)

X['unvoiced']['all'] = np.array(unvoiced)
Y['unvoiced']['all'] = np.array(df.loc[df['f0']==0].groupby(['file']).min().label.values)

np.random.seed(seed)

for type in ['voiced', 'unvoiced']:
n = len(X[type]['all'])
ind_rand = np.random.randint(n, size=int(train_percentage*n)) # random indices

return X, Y

X1, Y1 = train_test()

## 5. Train a classifer (k-NN method)

We used two implementations of a k-NN classifier, used both on voiced and unvoiced data:

1. Scikit Learn’s kNN classifier
2. our own implementation

We first use Scikit Learn’s kNN classifier to have a firsthand idea about the classification results. The code for Scikit Learn’s kNN classifier (with $k=3$) is shown below:

# Scikit Learn's kNN classifier:
# Just to test, but we will implement it ourselves of course!
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score

def sklearn_knn(k, X, Y):
for type in ['voiced', 'unvoiced']:
kNN = KNeighborsClassifier(n_neighbors=k)
kNN.fit(X[type]['train'], Y[type]['train'])

print("Accuracy score for {}: {:.2f}".format(type, accuracy_score(Y[type]['test'], kNN.predict(X[type]['test']))))
sklearn_knn(3, X1, Y1)

The classification result of Scikit Learn’s kNN classifier indicates that:

1. Accuracy score of voiced data = $0.91$
2. Accuracy score of unvoiced data = $0.61$

We can see that the accuracy of voiced data is 91%, much higher than the accuracy of unvoiced data which is only 61% (which confirms our previous intuition).

Then, we implement our own algorithm that we apply for both voiced and unvoiced data using the following code:

# Our own implementation!
from scipy.spatial.distance import cdist
from sklearn.metrics import confusion_matrix
from collections import Counter

def kNN(k, X, Y, labels=["pw", "ap"]):
# auxiliary function: label prediction (by majority vote)
# based on the nearest neighbors
def predicted_label(ind_neighbors):
label_neighbors = tuple(Y['train'][ind_neighbors])
return Counter(label_neighbors).most_common(1)[0][0]

# Pairwise distances between test and train data points
dist_matrix = cdist(X['test'], X['train'], 'euclidean')
y_predicted = []

for i in range(len(X['test'])):
ind_k_smallest = np.argpartition(dist_matrix[i, :], k)[:k]
y_predicted.append(predicted_label(ind_k_smallest))

# Confusion matrix: C[i, j] is the number of observations
# known to be in group i but predicted to be in group j
return confusion_matrix(Y['test'], np.array(y_predicted), labels=labels)

plt.figure()
cm = kNN(3, X1['voiced'], Y1['voiced'])
plot_confusion_matrix(cm, classes=["pw", "ap"],
title='Confusion matrix, with normalization')
plt.show()

cm2 = kNN(3, X1['unvoiced'], Y1['unvoiced'])
plot_confusion_matrix(cm2, classes=["pw", "ap"],
title='Confusion matrix, with normalization')
plt.show()

The result of our implementation is shown in Figure 3 and Figure 4:

Figure 3 shows that, using voiced segments as training data, the accuracy of the classifier is very high:

• $92$% accuracy for the prohibition class
• and $91$% accuracy for the approval class

Figure 4 demonstrates that, using unvoiced segments as training data, the accuracy of the classifier is worse:

• ony $49$% for the prohibition class
• and $77$% for the approval class

The results above, again, support that voiced segments are better for training the classifier, and that they enable us to faithfully (with more than $90$% accuracy) separate the data points based their label, with $k=3$.

## 6. Evaluate and discuss the performance of the classifier. You will discuss the relevance of the parameters (f0 et energy), the role of the functionals, the role of $k$, ratio of Learning/Test databases, random design of databases.

### Relevance of the parameters $f_0$ and energy

As shown in question 1.5, the classifier has relatively good results with voiced training data: more than $90$% of data points were correctly classified for each class. However, the results are more unsatisfactory with unvoiced training data: approximately $70$% of the approval data points and $50$% of the prohibition ones were correctly classified, which means that the recognition of prohibition data is more nettlesome than the recognition of approval data for unvoiced training data.

This better accuracy for voiced training data (which encompass the $f_0$ features, contrary to the unvoiced one), as well as the more separated data using $f_0$ shown in question 1.1.4, suggests that the $f_0$ parameter (the fundamental frequency) files may be more relevant/efficient than the energy to classify the sounds, provided that this fundamental frequency exists (which is the case for voiced sounds only).

### Role of the functionals

We have plotted some $f_0$ functionals as a function of others. Figure 5 and Figure 6 show the $f_0$ mean absolute of local derivate, and variance as a function of the mean. We found that expressing the variance as a function of the mean led to a better separation of the data points. As such, that these functionals come really in handy when it comes to classifying the data points by the k-NN method.

### Role of $k$

By implementing the k-NN classifier using different $k$ values, we found that with a higher $k$, the pw data can be classified more accurately, but the ap data will be classified less accurately. This may be due to larger values of $k$ reducing noise effect on the classification, but making boundaries between the classes less distinct.

### Ratio of Learning/Testing data

By testing the accuracy of classifier with different ratio values, we found that the classifier becomes less accurate for lower values of the ratio (due to a lack of training) and for larger values of the ratio as well (due to overfitting of the data).

# Exercice 2. Detection of multiple intents

## 1. Extract the prosodic features ($f_0$ and energy) and their functionals

Here, we use the same method than in question 1.1, using the pandas DataFrame df instead of df1:

df.groupby('file')['f0','en'].agg(list_features).head()

## 2. Develop a classifier for these three classses

We then develop a classifier which takes into account the third class (attention): this one corresponds to data points which are neither approvals nor prohibitions.

X, Y = train_test(df=df)
sklearn_knn(3, X, Y)
plt.figure()
cm = kNN(3, X['voiced'], Y['voiced'], labels=["pw", "ap", "at"])
plot_confusion_matrix(cm, classes=["pw", "ap", "at"],
title='Confusion matrix, with normalization')
plt.show()

cm2 = kNN(3, X['unvoiced'], Y['unvoiced'], labels=["pw", "ap", "at"])
plot_confusion_matrix(cm2, classes=["pw", "ap", "at"],
title='Confusion matrix, with normalization')
plt.show()

## 3. Evaluate and discuss the performance of the classifier. We could use confusion matrices.

As before, the classifier is more accurate for voiced segments than for unvoiced ones:

• for voiced segments:

• more than $80$% of the prohibition sounds
• $56$% of the approval ones
• and $66$% of the attention ones

were correctly classified.

• for unvoiced segments: the results are, as exepected, worse: only $51%$ of the prohibition, $45%$ of the approval and $37%$ of the attention sounds were correctly recognized.

On the whole:

• prohibition sounds are definitely the most recognizable ones, as indicated by the high corresponding accuracy rate
• however, the attention sounds seem to mess the approval class recognition up: the classifier has a harder time recognizing the approval sounds now that there are additional attention sounds. This has a rather intuitive explanation: one can conceive that it is easy to mistake an approval sentence with an attention-drawing one, as the tone of the voice generally rises in a similar fashion.

Tags:

Updated:

format: plain


text:
# Math Modeling : 5-Step Method

## Example Questions

### Example Question #1 : Optimization Models

A cow that weighs 175 pounds gains 3 pounds per day, and it costs 30 cents per day to keep that cow. The market price for cows is 75 cents per pound, but the price is falling one cent per day. When should the cow be sold to make the maximum profit?

Use the 5-step method.

The max profit is $151.58. The cow should be sold after 3 days. The cow should be sold after 4 days. The max profit is$131.58.

The cow should be sold after 2 days.

The cow should be sold after 3 days.

Explanation:

The 5-step method for this particular modeling question is as follows.

When should the cow be sold to make the maximum profit?

Now identify all known information.

Variables:

2. Select the modeling approach

For this particular question the function can be define  on a subset of the real number line. Therefore, take the derivative of  and set it equal to zero to calculate the maximum.

3. Formulate the model

To maximize  formulate the equation in terms of .

Now rewrite the equation in terms of .

4. Solve the model

Now to solve the model, take the derivative, set it equal to zero, and solve for .


text:
cf.Data.compressed¶

Data.compressed(inplace=False)[source]

Return all non-masked values in a one dimensional data array.

Not to be confused with compression by convention (see the uncompress method).

New in version 3.2.0.

Parameters
inplace: bool, optional

If True then do the operation in-place and return None.

Returns
Data or None

The non-masked values, or None if the operation was in-place.

Examples

>>> d = cf.Data(numpy.arange(12).reshape(3, 4))
>>> print(d.array)
[[ 0  1  2  3]
[ 4  5  6  7]
[ 8  9 10 11]]
>>> print(d.compressed().array)
[ 0  1  2  3  4  5  6  7  8  9 10 11]

>>> d = cf.Data(9)


text:
# Multiplying summations?

Luongo
1. on #1 c) of the homework:
http://www.math.ubc.ca/~oyilmaz/courses/m267/hmk3.pdf [Broken]
how do i multiply this summation?

## Homework Equations

3. what i did was i multiplied the 2 expos and made on of the k indexes a 'm' instead and i got $$\sum ei(k+m)t$$

Last edited by a moderator:

praharmitra
$$\left( \sum_{k =1}^{N_1} f(k) \right) \left( \sum_{j=1}^{N_2} g(j) \right) = \sum_{k=1}^{N_1} \sum_{j=1}^{N_2} f(k)g(j)$$

Can you try to see why the above is true?

Now in your problem, k is a dummy variable (meaning, that since it sums over, it doesn't matter if we call it k, or j). So we can replace the variable in the second summation, by j. Then you can apply the above formula.


text:
# 35.5 The subset-sum problem

## 35.5-1

Prove equation $\text{(35.23)}$. Then show that after executing line 5 of $\text{EXACT-SUBSET-SUM}$, $L_i$ is a sorted list containing every element of $P_i$ whose value is not more than $t$.

(Omit!)

## 35.5-2

Using induction on $i$, prove inequality $\text{(35.26)}$.

(Omit!)

## 35.5-3

Prove inequality $\text{(35.29)}$.

(Omit!)

## 35.5-4

How would you modify the approximation scheme presented in this section to ﬁnd a good approximation to the smallest value not less than $t$ that is a sum of some subset of the given input list?

(Omit!)

## 35.5-5

Modify the $\text{APPROX-SUBSET-SUM}$ procedure to also return the subset of $S$ that sums to the value $z^*$.

(Omit!)


text:
A A A O O L I

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

A A A O O L I

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

A A A O O L I

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

A A A O O L I

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

A A A O O L I

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

A A A O O L I

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

A A A O O L I

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

A A A O O L I
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

A A A O O L I

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

A A A O O L I

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

A A A O O L I

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

A A A O O L I

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31


text:
# GRE GR 1777, Problem 011 Solution

Physics GRE GR 1777
11. Quantum Mechanics (Characteristic X-rays)
By definition in the Wikipedia, characteristic X-rays are emitted when outer-shell electrons fill a vacancy in the inner shell of an atom, releasing X-rays in a pattern that is “characteristic” to each element.
Therefore, the answer is (C).
Tips) Actually, I didn’t see this in my QM textbooks. So the only way to solve the problem was to memorize this phenomenon from the Internet search. If I would find the better way to solve the problem, I will post it.
References)
https://en.wikipedia.org/wiki/Characteristic_X-ray
http://hyperphysics.phy-astr.gsu.edu/hbase/quantum/xrayc.html


text:
# Hamiltonicity of k-regular graphs

It is known that it is NP-complete to test whether a Hamiltonian cycle exists in a 3-regular graph, even if it is planar (Garey, Johnson, and Tarjan, SIAM J. Comput. 1976) or bipartite (Akiyama, Nishizeki, and Saito, J. Inform. Proc. 1980) or to test whether a Hamiltonian cycle exists in a 4-regular graph, even when it is the graph formed by an arrangement of Jordan curves (Iwamoto and Toussaint, IPL 1994).

For which other k is it known to be NP-complete to test Hamiltonicity of k-regular graphs?

The particular case I am interested in is 6-regular graphs, with the additional condition that the graph have an odd number of vertices. If this case could be shown to be NP-complete (or polynomial) it would have impact in a graph drawing problem described in http://arxiv.org/abs/1009.0579 . The "odd number of vertices" condition is because what I really want to know is, for 6-regular graphs, whether the graph contains either a Hamiltonian cycle or a bipartite 2-factor; but having an odd number of vertices eliminates the possibility of a bipartite 2-factor leaving only the possibility of a Hamiltonian cycle.

First step let assume the graph has even number of vertices. In the second stage, we will extend the construction, so that if k is even, then we will show how to turn the graph into having odd number of vertices.

The solution is a refinement of the idea suggested in the other answer.

## First part

Claim: Given a $k$-regular graph $G$ with even number of vertices, one can compute a graph $H$ which is $(k+1)$-regular, and $H$ is Hamiltonian iff $G$ is Hamiltonian.

Proof: Take two copies of the $k$-regular graph $G$, let call them $G_1$ and $G_2$. For a vertex $v \in V(G)$, let $v_1$ and $v_2$ be the corresponding copies. Create a clique with $k+2$ vertices for $v$. Pick two vertices $v'$ and $v''$ in this clique, and remove the edge between them. Next, connect $v_1$ to $v'$ and $v_2$ to $v''$. Let $C(v)$ denote this component for $v$.

Repeat this for all the vertices of $G$, and let $H$ denote the resulting graph.

Clearly, the graph $H$ is $k+1$ regular. We claim that $H$ is Hamiltonian if and only if $G$ is Hamiltonian.

One direction is clear. Given a Hambiltonian cycle in $G$, we can translate it into a cycle in $H$. Indeed, whenever the cycle visits a vertex $v$, we interpret it as moving from $v_1$ to $v_2$ (or vice versa) while visiting all the vertices in $C(v)$. As such, this results in a Hamiltonian cycle in $H$. (Note, that this is where we are using the fact that the original number of vertices is even - if the cycle is odd this breaks down.)

As for the other direction, consider a Hamiltonian cycle in $H$. It must be that $C(v)$ is visited by a portion of the cycle that starts in $v_1$, visits all the vertices of $C(v)$ and leaves from $v_2$ (or the symmetric option). Indeed, the Hamiltonian cycle can not enter and leave from the same $v_i$. As such, a Hamiltonian cycle in $H$ as a natural interpretation as a Hamiltonian cycle in $G$. QED.

## Second part

As noted below by Tsuyoshi any 3-regular graph has even number of vertices. As such, the problem is hard for a $3$-regular graph with even number of vertices. Namely, the above reduction shows the problem is hard for any $k$-regular graph, although the resulting graph has an even number of vertices.

We observe, that this implies that the following problem is NP-hard.

Problem A: Deciding if a k-regular graph $G$ with even number of vertices has an Hamiltonian cycle going through a specific edge $e$.

However, if $k$ is even then given an instance $(G, e)$ we can reduce it to desired problem. Indeed, we replace the edge $e$ by a clique of $k+1$ vertices, as before deleting one edge in the clique, and connecting its two endpoints to the endpoints of $e$, and removing $e$ from the graph. Clearly, for the new graph $H$:

• $H$ is $k$-regular.
• $H$ is Hamiltonian iff $G$ is Hamiltonian with a cycle using $e$.
• $H$ has $|V(G)| + k+1$ vertices => $H$ has odd number of vertices.

Note, that a $k$-regular graph, for $k$ odd, must have an even number of vertices (just count the edges), As such, there are no $k$-regular graphs with odd number of vertices, with $k$ being odd.

## Result

It is NP-Hard to decide if a $k$-regular graph has a Hamiltonian cycle for $k\geq 3$. The problem remains NP-Hard even if the graph has an odd number of vertices.

Of course, it is always possible I made some stupid mistake...

## Exercise

If we want to go from a graph that is $k$-regular to a graph that is (say) $2k$-regular then the graph resulting from applying the above reduction repeatedly results in a graph with a size that depends exponentially on $k$. Show, that given a $k$-regular graph $G$, and $i >2$, one can construct a graph $H$ that is $(k+i)$-regular and its size is polynomial in $k,i$ and $n$, where $n$ is the number of vertices of $G$. Furthermore, $G$ is Hamiltonian if and only if $H$ is Hamiltonian.

(I am posting this as an exercise, not a question, since I know how to solve this.)

• Great! I think that this answer in fact settles the first question “For which other k is it known to be NP-complete to test Hamiltonicity of k-regular graphs?” because the 3-regular graphs have an even number of vertices, and the graph H made by this transformation also has an even number of vertices if G has an even number of vertices. – Tsuyoshi Ito Sep 25 '10 at 1:57
• But unless I'm mistaken, the same counter-example to Robin's proof is a counter-example to this proof. Let G be the path on 2 vertices. Then the procedure here creates H, which is a 9 cycle, which is Hamiltonian. – Emil Sep 25 '10 at 10:37
• As I said in regard to Robin's answer, the problem is that when you try to "project" the Hamilton cycle from H on to G, the cycle may end up not being a cycle, because it retraces where it has been. – Emil Sep 25 '10 at 10:40
• @Emil: I think that the path on 2 vertices is really a special case because it has a Hamiltonian circuit if we are allowed to use the same edge more than once. – Tsuyoshi Ito Sep 25 '10 at 11:52
• @Sariel Har-Peled: In every graph, the number of odd vertices (i.e. vertices of odd degree) is even. Therefore, all the 3-regular graphs have an even number of vertices. I had written an unnecessarily complicated argument without realizing this in the first version of comment (which I modified in less than 5 minutes), so excuse me if you read my old comment and were confused by it. – Tsuyoshi Ito Sep 25 '10 at 11:56

EDIT: This proof is wrong, as pointed out in the comments. (Should I delete the post?)

It intuitively feels like if Hamiltonicity is NP-hard for k-regular graphs, then it should also be NP-hard for (k+1)-regular graphs. Here's a back-of-the-envelope reduction, which looks fine to me, but of course there could be a mistake.

Let G be a k-regular graph. Let G' be a the graph Cartesian product of G and an edge. In other words, G' is the graph which has two copies of G, and every vertex is connected to its copy. G' is now (k+1) regular, since each vertex got 1 extra edge.

Claim: G has a Hamiltonian cycle if and only if G' has a Hamiltonian cycle.

Proof: If G has a Hamiltonian cycle, it's easy to see that G' has one too. Say (u,v) is an edge in the Hamiltonian cycle. Traverse the cycle from u to v without using that edge, and now instead of using the edge, go to v' from v, where v' is the vertex corresponding to v in the copy of G. Now traverse the cycle in the reverse order in this graph, which will bring us back to u'. Now go from u' to u, which completes the cycle.

If G' has a Hamiltonian cycle starting from vertex u, consider the same sequence of traversals on G. Every time a move is made to an adjacent vertex in the same graph, we make the same move in G. Every time a move is made to the corresponding vertex in the other graph, we do nothing. Since every move is valid on the graph G, and the cycle ends on vertex u, this is a Hamiltonian cycle.

• I cannot see how the second paragraph of the proof works. If we drop the condition that G is k-regular, letting G be a path gives a counterexample to a claim that if G′ is Hamiltonian then G is also Hamiltonian. – Tsuyoshi Ito Sep 24 '10 at 23:10
• I'm a bit concerned about the last paragraph here. When the Hamilton cycle for G' is "projected" (if that is the right word!) on to G, we may have a situation where the cycle retraces its steps. – Emil Sep 24 '10 at 23:11
• @Tsuyoshi: you have got a counter-example: just take a regular path - the path with two vertices. – Emil Sep 24 '10 at 23:24
• @Tsuyoshi: You're right. The proof is wrong. Should I delete the answer? Do we have a policy on this? – Robin Kothari Sep 24 '10 at 23:27
• @Robin, I think your post should be left now that it has generated some discussion. It certainly illustrates that this is an awkward problem. – Emil Sep 24 '10 at 23:52


text:
# Chapter 8 - Polynomials and Factoring - Chapter Test: 15

GCF=$v^{2}$

#### Work Step by Step

Find the GCF of the terms of each polynomial. $7v^{3}-10v^{2}+9v^{4}$ All of the terms are divisible by $v^{2}$ so the GCF must contain $v^{2}$ The coefficients don't have a common factor. GCF=$v^{2}$ All of the terms are divisible by $v^{2}$

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.


text:
# Fibonacci coding

In mathematics and computing, Fibonacci coding is a universal code[citation needed] which encodes positive integers into binary code words. It is one example of representations of integers based on Fibonacci numbers. Each code word ends with "11" and contains no other instances of "11" before the end.

The Fibonacci code is closely related to the Zeckendorf representation, a positional numeral system that uses Zeckendorf's theorem and has the property that no number has a representation with consecutive 1s. The Fibonacci code word for a particular integer is exactly the integer's Zeckendorf representation with the order of its digits reversed and an additional "1" appended to the end.

## Definition

For a number ${\displaystyle N\!}$, if ${\displaystyle d(0),d(1),\ldots ,d(k-1),d(k)\!}$ represent the digits of the code word representing ${\displaystyle N\!}$ then we have:

${\displaystyle N=\sum _{i=0}^{k-1}d(i)F(i+2),{\text{ and }}d(k-1)=d(k)=1.\!}$

where F(i) is the ith Fibonacci number, and so F(i+2) is the ith distinct Fibonacci number starting with ${\displaystyle 1,2,3,5,8,13,\ldots }$. The last bit ${\displaystyle d(k)}$ is always an appended bit of 1 and does not carry place value.

It can be shown that such a coding is unique, and the only occurrence of "11" in any code word is at the end i.e. d(k−1) and d(k). Note that the penultimate bit is the most significant bit and the first bit is the least significant bit. Note also that leading zeros cannot be omitted as they can in e.g. decimal numbers.

The first few Fibonacci codes are shown below, and also the so-called implied probability distribution, the distribution of values for which Fibonacci coding gives a minimum-size code.

Symbol Fibonacci representation Fibonacci code word Implied probability
1 ${\displaystyle F(2)}$ 11 1/4
2 ${\displaystyle F(3)}$ 011 1/8
3 ${\displaystyle F(4)}$ 0011 1/16
4 ${\displaystyle F(2)+F(4)}$ 1011 1/16
5 ${\displaystyle F(5)}$ 00011 1/32
6 ${\displaystyle F(2)+F(5)}$ 10011 1/32
7 ${\displaystyle F(3)+F(5)}$ 01011 1/32
8 ${\displaystyle F(6)}$ 000011 1/64
9 ${\displaystyle F(2)+F(6)}$ 100011 1/64
10 ${\displaystyle F(3)+F(6)}$ 010011 1/64
11 ${\displaystyle F(4)+F(6)}$ 001011 1/64
12 ${\displaystyle F(2)+F(4)+F(6)}$ 101011 1/64
13 ${\displaystyle F(7)}$ 0000011 1/128
14 ${\displaystyle F(2)+F(7)}$ 1000011 1/128

To encode an integer N:

1. Find the largest Fibonacci number equal to or less than N; subtract this number from N, keeping track of the remainder.
2. If the number subtracted was the ith Fibonacci number F(i), put a 1 in place i−2 in the code word (counting the left most digit as place 0).
3. Repeat the previous steps, substituting the remainder for N, until a remainder of 0 is reached.
4. Place an additional 1 after the rightmost digit in the code word.

To decode a code word, remove the final "1", assign the remaining the values 1,2,3,5,8,13... (the Fibonacci numbers) to the bits in the code word, and sum the values of the "1" bits.

## Comparison with other universal codes

Fibonacci coding has a useful property that sometimes makes it attractive in comparison to other universal codes: it is an example of a self-synchronizing code, making it easier to recover data from a damaged stream. With most other universal codes, if a single bit is altered, none of the data that comes after it will be correctly read. With Fibonacci coding, on the other hand, a changed bit may cause one token to be read as two, or cause two tokens to be read incorrectly as one, but reading a "0" from the stream will stop the errors from propagating further. Since the only stream that has no "0" in it is a stream of "11" tokens, the total edit distance between a stream damaged by a single bit error and the original stream is at most three.

This approach - encoding using sequence of symbols, in which some patterns (like "11") are forbidden, can be freely generalized [1].

## Example

The following table shows that the number 65 is represented in Fibonacci coding as 0100100011, since 65 = 2 + 8 + 55. The first two Fibonacci numbers (0 and 1) are not used, and an additional 1 is always appended.

 0 1 1 2 3 5 8 13 21 34 55 – ${\displaystyle F(0)}$ ${\displaystyle F(1)}$ ${\displaystyle F(2)}$ ${\displaystyle F(3)}$ ${\displaystyle F(4)}$ ${\displaystyle F(5)}$ ${\displaystyle F(6)}$ ${\displaystyle F(7)}$ ${\displaystyle F(8)}$ ${\displaystyle F(9)}$ ${\displaystyle F(10)}$ additional – – 0 1 0 0 1 0 0 0 1 1

## Generalizations

The Fibonacci encodings for the positive integers are binary strings that end with "11" and contain no other instances of "11". This can be generalized to binary strings that end with N consecutive 1's and contain no other instances of N consecutive 1's. For instance, for N = 3 the positive integers are encoded as 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, …. In this case, the number of encodings as a function of string length is given by the sequence of Tribonacci numbers.


text:
• 学术论文 •

### 一种基于峭度累积量比例微分控制的盲源分离学习率

1. 福建师范大学福清分校电子与信息工程学院, 福建福清 350300
• 收稿日期:2014-07-02 修回日期:2014-10-29 出版日期:2015-05-25
• 作者简介:
• 陈国钦 男,1962年生于福建永春.现为福建师范大学福清分校电子与信息工程学院副教授.主要研究为方向电子、通信和信号处理.E-mail:cgq6203@163.com
• 基金资助:
• 福建省教育厅A类重点项目 (No.JA13341)

### A Learning Rate in Blind Source Separation Based on Proportional Differential Control of Kurtosis Cumulative

CHEN Guo-qin

1. School of Electronic and Information Engineering, Fuqing Branch of Fujian Normal University, Fuqing, Fujian 350300, China
• Received:2014-07-02 Revised:2014-10-29 Online:2015-05-25 Published:2015-05-25

Abstract:

Natural gradient algorithm occupies an important position in blind source separation due to its good separation performance,but when the algorithm is based on a fixed-step size,a good balance will impossibly be achieved between the convergence rate and steady-state error.This article drew PID (Proportion Integration Differentiation) algorithm of automation control as a reference and proposed an algorithms in variable-step learning rate closely integrated with the state of separation.Due to the fact the cumulative amount of the signal kurtosis was an intrinsic value after the complete separation,there arose a gradually decreasing error value between the cumulative amount of the signal kurtosis of the separation process and the inherent value.The exponential function value of e in the algorithm was applied to reflect the error value.Then the error was used to constitute proportional differential variable-step algorithm,among which the initial value of the step was equivalent to proportional value of the error control,and the differential term of the error gained the adjusted values in acceleration.The simulation results show that corresponding to a maximum and a minimum of step initial value,the number of iterations of the algorithm in two times was lower than that of iterations with fixed-step algorithm,and the difference between the two iterations was about 10 to 40 times for signals of different type,however,the steady-state error of the two algorithms was the same.


text:
### Multi-Client Oblivious RAM with Poly-Logarithmic Communication

Sherman S. M. Chow, Katharina Fech, Russell W. F. Lai, and Giulio Malavolta

##### Abstract

Oblivious RAM enables oblivious access to memory in the single-client setting, which may not be the best fit in the network setting. Multi-client oblivious RAM (MCORAM) considers a collaborative but untrusted environment, where a database owner selectively grants read access and write access to different entries of a confidential database to multiple clients. Their access pattern must remain oblivious not only to the server but also to fellow clients. This upgrade rules out many techniques for constructing ORAM, forcing us to pursue new techniques. MCORAM not only provides an alternative solution to private anonymous data access (Eurocrypt 2019) but also serves as a promising building block for equipping oblivious file systems with access control and extending other advanced cryptosystems to the multi-client setting. Despite being a powerful object, the current state-of-the-art is unsatisfactory: The only existing scheme requires $O(\sqrt n)$ communication and client computation for a database of size $n$. Whether it is possible to reduce these complexities to $\mathsf{polylog}(n)$, thereby matching the upper bounds for ORAM, is an open problem, i.e., can we enjoy access control and client-obliviousness under the same bounds? Our first result answers the above question affirmatively by giving a construction from fully homomorphic encryption (FHE). Our main technical innovation is a new technique for cross-key trial evaluation of ciphertexts. We also consider the same question in the setting with $N$ non-colluding servers, out of which at most $t$ of them can be corrupt. We build multi-server MCORAM from distributed point functions (DPF), and propose new constructions of DPF via a virtualization technique with bootstrapping, assuming the existence of homomorphic secret sharing and pseudorandom generators in NC0, which are not known to imply FHE.

Available format(s)
Publication info
DOI
10.1007/978-3-030-64834-3_6
Keywords
multi-client oblivious RAMaccess controlhomomorphic encryptiondistributed point functionhomomorphic secret sharing
Contact author(s)
sherman @ ie cuhk edu hk
fech @ cs fau de
lai @ cs fau de
giulio malavolta @ hotmail it
History
Short URL
https://ia.cr/2020/1551

CC BY

BibTeX

@misc{cryptoeprint:2020/1551,
author = {Sherman S.  M.  Chow and Katharina Fech and Russell W.  F.  Lai and Giulio Malavolta},
title = {Multi-Client Oblivious RAM with Poly-Logarithmic Communication},
howpublished = {Cryptology ePrint Archive, Paper 2020/1551},
year = {2020},
doi = {10.1007/978-3-030-64834-3_6},
note = {\url{https://eprint.iacr.org/2020/1551}},
url = {https://eprint.iacr.org/2020/1551}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.


text:
# zbMATH — the first resource for mathematics

Vortex equation and reflexive sheaves. (English) Zbl 1270.53063
Given a stable holomorphic pair $$(E,\phi)$$, where $$E$$ is a holomorphic vector bundle on a compact Kähler manifold $$X$$ and $$\phi$$ is a holomorphic section of $$E$$, the vector bundle $$E$$ admits a Hermitian metric solving the vortex equation. This is generalized to pairs $$(\mathcal{E},\phi)$$, where $$\mathcal{E}$$ is a reflexive sheaf on $$X$$, see also [S. B. Bradlow, Commun. Math. Phys. 135, No. 1, 1–17 (1990; Zbl 0717.53075); G. Tian and B. Yang, J. Reine Angew. Math. 553, 17–41 (2002; Zbl 1022.53025)].
##### MSC:
 53C07 Special connections and metrics on vector bundles (Hermite-Einstein, Yang-Mills) 53B35 Local differential geometry of Hermitian and Kählerian structures
##### Keywords:
stable holomorphic pair; Hermitian metric; vortex equation
Full Text:


text:
# Do we have a better understanding of what energy is since Feynman's time?

When lecturing about conservation of energy in the 1960s, Richard Feynman remarked:

It is important to realize that in physics today, we have no knowledge of what energy is. We do not have a picture that energy comes in little blobs of a definite amount. It is not that way. However, there are formulas for calculating some numerical quantity, and when we add it all together it gives “28” —always the same number. It is an abstract thing in that it does not tell us the mechanism or the reasons for the various formulas. [1]

50 some years later, have we made any progress in terms of understanding the fundamental nature of what energy is?

• Similar question: physics.stackexchange.com/q/217495 – Mark H Apr 12 '16 at 4:56
• As mentioned in MarkH's link, energy serves a similar function in physical systems as money does in accounting systems (and both are subject to similar strictures). It cannot be isolated into a discrete object, but is a common unit that quantifies relations between physical things. Therefore, as Feynman implies, there isn't any work to do on understanding it's fundamental nature - though we accept relations, a relation cannot be held in the hand without noticing that it consists of multiple component parts - and the relation seems to exist between both parts, not inherently in either part. – Steve Feb 9 '18 at 11:50
• 28 what? 28 giga joule? what? – user4951 Mar 11 '18 at 18:14
• Your "what" is Feynman's point. There is presently no fundamental blob (or constant) of energy to have 28 of. – Gary Godfrey Mar 28 '19 at 22:33

I can misquote:

"It is important to realize that in physics today, we have no knowledge of what space is."

What we know at present is that energy is part of a coordinate system defining a Lorenz four vector, the same way that space and time define another four vector.

We have a system of differential equations and the necessary mathematical tools to be able to model observations and data consistently and predict measurements for new setups successfully.

When one has an axiomatic mathematical theory, one accepts the axioms . Questioning them makes no sense, since they are necessary for that particular mathematical theory.

Lorenz invariance and coordinate systems, together with the postulates of quantum mechanics are necessary extra axioms introduced into physics theories for mathematically modeling data, the models also predictive of new experimental measurements. That is where our knowledge is at present.

Energy is defined as one of the coordinates of the energy-momentum vector. If this is progress from 60 years ago, I cannot tell. I can tell that further meditations belong to philosophy and metaphysics.

• You show us what math tools we use to analyze energy. Energy can be represented, for calculation purposes by certain mathematical objects. I'm not sure that addresses the question of what energy is. – garyp Mar 28 '19 at 18:47
• @garyp I thought I was clear that energy is axiomatic, the way space is axiomatic, i.e. not further analyzable? – anna v Mar 28 '19 at 19:10

I suspect he was saying that we are in the same predicament 19th century physicists were in about understanding temperature. During the 19th century, the laws of thermodynamics, which included temperature, were defined and validated even though there was no understanding as to the source of temperature. At that time, no reliable scientist believed in the existence of atoms. It was only after the beginning of the 20th century that Einstein, Bohr and other physicists proved the existence of atoms and molecules and showed that temperature is the result of their random motions. We currently have no similar understanding as to the source of energy

• Boltzmann understood entropy and temperature in terms of atoms well before Einstein. – Peter Shor Mar 29 '19 at 1:09

I think Feynman's point was that there is no fundamental blob of energy (or a physical constant) which all other blobs can be explained as a multiple of. Perhaps he had in his head the successful example of angular momentum where every blob of angular momentum in the universe is understood as a multiple of the fundamental constant $$\hbar$$ via the math of the rotation group.

In the years since Feynman's passing (Feb, 1988), we still have 3 generations of quarks and leptons, but neutrinos are no longer massless and the Higgs has been discovered, so the zoo of seemingly fundamental blobs of energy has changed/expanded...but there is still no theory successfully relating all the blobs to a fundamental constant of energy. Feynman knew about the one energy constant, the Planck mass, that can be constructed from our fundamental constants ($$m_{Planck}=\sqrt{\frac{\hbar c}{G}}=10^{19}\quad GeV$$) but like everyone else could not calculate (~1 GeV) elementary particle masses from it. Perhaps the measurement of a non-zero Cosmological constant (which might actually be constant in space and time?) qualifies as a bit of progress since we now have a second energy constant ($$\hbar c \sqrt{\Lambda}=10^{-42}\quad GeV$$) to try to explain particle masses.

Energy is electrostatic motive force carried by moving matter and vibrating electrons/atoms.

Energy must coexisting with matter. Therefore there is no light wave, no photon particle traveling in space at light speed.

All theories based on light speed in space is C are mistaken.


text:
## Why is it so hard to prove that e+pi or e*pi is irrational/rational?

The reason why it is so hard to prove is actually very easy to answer. These constants, identities, and variations being referred to in this post, and others like it, all lay embedded in a far deeper substrate than current mathematics has yet explored.

Mathematics has been, and always shall be my ‘first love’, and it has provided for me all of these years. I am not criticising mathematics in any way. It is my firm belief that mathematics will overcome this current situation and eventually be quite able to examine these kinds of questions in a much more expansive and deeper way.

We need to extend our examination of mathematical knowledge, both in depth and in scope, out farther and in deeper than numbers (sets and categories as well – even more below) have yet done. I’ll introduce you to a pattern you may have already noticed in the current stage of our mathematical endeavour.

We all know there are numbers which lay outside of Q which we call Irrational numbers. There are also numbers which lay outside of R which we call Imaginary numbers. They have both been found, because the domain of questioning exceeded the range of answers being sought within the properties each of those numbers. This pattern continues in other ways, as well.

We also know there are abstractions and/or extensions of Complex numbers where the ‘air starts to get thin’ and mathematical properties start to ‘fade away’: Quaternions, Octonians, Sedenions,…

This pattern continues in other ways: Holors, for example, which extend and include mathematical entities such as Complex numbers, scalars, vectors, matrices, tensors, Quaternions, and other hypercomplex numbers, yet are still capable of providing a different algebra which is consistent with real algebra.

The framing of our answers to mathematical questions is also evolving. Logic was, for example, limited to quite sophisticated methods that all were restricted to a boolean context. Then we found other questions which led to boundary, multi-valued, fuzzy, and fractal logics, among a few others I haven’t mentioned yet.

Even our validity claims are evolving. We are beginning to ask questions which require answers which transcend relationship properties such as causality, equivalence, and inference in all of their forms. Even the idea of a binary relationship is being transcended into finitary versions (which I use in my work). There are many more of these various patterns which I may write about in the future.

They all have at least one thing in common: each time we extend our reach in terms of scope or depth, we find new ways of seeing things which we saw before and/or see new things which were before not seen.

There are many ‘voices’ in this ‘mathematical fugue’ which ‘weaves’ everything together: they are the constants, variations, identities, and the relationships they share with each other.

The constants e, π, i, ϕ, c, g, h  all denote or involve ‘special’ relationships of some kind. Special in the sense that they are completely unique.

For example:

• e is the identity of change (some would say proportion, but that’s not entirely correct).
• π is the identity of periodicity. There’s much more going on with $\pi$ than simply being a component of arc or, in a completely different context, a component of area

These relationships actually transcend mathematics. Mathematics ‘consumes’ their utility (making use of those relationships), but they cannot be ‘corralled in’ as if they were ‘horses on the farm’ of mathematics. Their uniqueness cannot be completely understood via equivalence classes alone.

• They are ubiquitous and therefore not algebraic.
• They are pre-nascent to number, equivalence classes, and validity claims and are therefore not rational.

These are not the only reasons.

It’s also about WHERE they are embedded in the knowledge substrate compared to the concept of number, set, category…. They lay more deeply embedded in that substrate.

The reason why your question is so hard for mathematics to answer is, because our current mathematics is, as yet, unable to decide. We need to ‘see’ these problems with a more complete set of ‘optics’ that will yield them to mathematical scrutiny.

Question on Quora

## Is the P=NP Problem an NP Problem?

What I’m going to say is going to be unpopular, but I cannot reconcile my own well-being without giving you an answer to this problem from my perspective.

My only reason for reluctantly writing this, knowing what kind of reaction I could receive is, because I abhor that some of the best minds on our planet are occupying themselves with this problem. It pains me to no end to see humanity squandering its power for a problem that, as it is currently framed, is unanswerable. It goes further than this though. There will come a time when questions such as this one will be cast upon the junk heap of humanity’s growth throughout history. It will take its rightful place along such ideas as phrenology.

Here’s why I say this:

The problem is firmly and completely embedded in Functional Reductionism. I say this, because the problem’s framing requires us to peel away the contextual embedding of the problems for which it is supposed to clarify.

This is just one of its problems. Here’s another:

Since the data for this problem (and those like it) are themselves algorithms, they are compelled to be functionally reduced versions of mind problem solving (varying types of heuristics and decision problems) which reduces the problem’s causal domain and its universe of discourse even further. How can a specification based upon functionally reduced data be again used as data for the problem’s solution in the first place?

That means that this problem has no independent existence nor causal efficacy. Everywhere I have looked at this problem, the definitions of NP-Hard and NP-Complete do not lead to proving anything useful. We cannot ‘generalise’ the mind by reducing it to some metric of complexity. Complexity is also not how the universe works as Occam’s Razor[1] shows.

I am prepared to defend my position should someone have the metal to test me on this. Another thing: I wish I could have left this alone, but we all need to wake up to this nonsense.

[1] http://bit.ly/2GHbRkW How Occam’s Razor Works

[Quora] http://bit.ly/2EuRdP3

This system is quite interesting if we allow ourselves to talk about the qualities of infinite sets as if we can know their character completely. The problem is, any discussion of an infinite set includes their definition which MAY NOT be the same as any characterisation which they may actually have.

Also, and more importantly, interiority as well as exteriority are accessible without the use of this system. These ‘Hyperreals’ are an ontological approach to epistemology via characteristics/properties we cannot really know. There can be no both true and verifiable validity claim in this system.

## Knowledge Representation – Holographic Heart Torus

Holographic Heart Torus by Ryan Cameron on YouTube

## Are sets, in an abstract sense, one of the most fundamental objects in contemporary mathematics?

Yes and no.

The equivalence relation lies deeper within the knowledge representation and it’s foundation.

There are other knowledge prerequisites which lie even deeper within the knowledge substrate than the equivalence relation.

The concepts of a boundary, of quantity, membership, reflexivity, symmetry, transitivity, and relation are some examples.

http://bit.ly/2wPV7RN

## Limits of Category Theory and Semiotics

They are wonderful tools to explain much of our world, but lack ‘The Right Stuff’ to handle the metaphysical underpinnings of anything near a Philosophy of Mind, Philosophy of Language , or a Philosophy of Learning.

This is, because Category Theory specialises on roughly half of the Noosphere. It does a wonderful job on exteriority, but cannot sufficiently describe nor comprehensively access interiority.

Therefore, as is the case with Semiotics, has limited metaphysical value with respect to philosophy in general.

For example: philosophies of mind, language, or learning are not possible using only category theoretical tools and/or semiotics.

Here is an example of one attempt which fails in this regard: http://nickrossiter.org.uk/proce…

(and here: VisualizationFoundationsIEEE)

Here are two problems (of many) in the paper:

4.4.2 Knowledge is the Terminal Object of Visualisation states:

“The ultimate purpose of the visualisation process is to gain Knowledge of the original System. When this succeeds (when the diagram commutes) then the result is a ‘truth’ relationship between the Knowledge and the System. When this process breaks down and we fail to deduce correct conclusions then the diagram does not commute.”

I want to also comment on Figure 3 (which also exposes missing or false premises in the paper), but I will wait until I have discussed the assertions in the quote above which the authors of this paper reference, accept, and wish to justify/confirm.

1) The purpose of a representation is NOT to gain knowledge; rather, to express knowledge. Also, truth has nothing to do with knowledge except when that value is imposed upon it for some purpose. Truth value is a value that knowledge may or not ‘attend’ (participate in).

1a) The ‘truth value’ of the System (‘system’ is a false paradigm [later, perhaps] and a term that I also vehemently disagree with) does not always enter into the ‘dialogue’ between any knowledge that is represented and the observer interpreting that knowledge.

2) The interpretation of a representation is not to “deduce correct conclusions”; rather, to understand the meaning (semantics and epistemology) of what is represented. ‘Correct’ understanding is not exclusive to understanding nor is it necessary or sufficient for understanding a representation, because that understanding finds expression in the observer.

2a) ‘Correct’, as used in this paragraph, is coming from the outside (via the choice of which data [see Fig. 3] is represented to the observer) and may have no correspondence (hence may never ever commute) whatever to what that term means for the observer.

The authors are only talking about ontologies. That is a contrived and provincial look at the subject they are supposing to examine.

There may (and usually are) artefacts inherent in any collection and collation of data. The observer is forced to make ‘right’ (‘correct’) conclusions from that data which those who collected it have ‘seeded’ (tainted) with their own volition.

‘System’ (systematising) anything is Reductionism. This disqualifies the procedure at its outset.

They are proving essentially that manipulation leads to a ‘correct’ (their chosen version) representation of a ‘truth’ value.

I could tie my shoelaces into some kind of knot and think it were a ‘correct’ way to do so if the arrows indicate this. This is why paying too much attention to a navigation system can have one finding themselves at the bottom of a river!

The paper contains assumptions that are overlooked and terms that are never adequately defined! How can you name variables without defining their meaning? They then serve no purpose and must be removed from domain of discourse.

Categorical structures are highly portable, but they can describe/express only part of what is there. There are structure, dynamics, and resonance that ontology and functionalism completely turns a blind eye to.

The qualities of Truth, Goodness, Beauty, Clarity,… (even Falsehood, Badness, Ugliness, Obscurity,…) can be defined and identified within a knowledge representation if the representation is not restricted to ontology alone.

In order to express these qualities in semiotics and category theory, they must first be ontologised funtionally (reduced). Trying to grasp them with tools restricted to semiotics and category theory is like grasping into thin air.

That is actually the point I’m trying to make. Category Theory, and even Semiotics, each have their utility, but they are no match for the challenge of a complete representation of knowledge.

## Universal Constants, Variations, and Identities #19 (Inverse Awareness)

Universal Constants, Variations, and Identities
#19 The Inverse Awareness Relation

The Inverse Awareness Relation establishes a fundamental relationship in our universe:

Micro Awareness = $\dfrac{1}{scope}$

and

Macro Awareness = $\dfrac{1}{depth}$
or

$\dfrac {Micro Awareness}{Macro Awareness} = \dfrac{depth}{scope}$

Which essentially state:

The closer awareness is in some way to an entity, the more depth and the less scope it discerns.

The farther awareness is in some way to an entity, the more scope and the less depth it discerns.

(Be careful, this idea of closeness is not the same as distance.)


text:
# proving no primitive roots exist modulo $2^n$ for n $\geq$ 3

Ive been asked to prove by induction that no primitive roots exist modulo $$2^n$$ for n $$\geq$$ 3.

I have proven true for base case $$n=3$$, and assumed to be true for $$n$$. I'm now stuck at this point:

$${x^{2}}^{n-1} \equiv 1 \pmod{2^{n+1}}.$$

thank you :)

• If there were a primitive root mod $2^{n + 1}$ then that same root would be a primitive root mod $2^n$. Oct 31, 2021 at 21:51
• hey man, thanks for the help- im still struggling to see how i can use that to prove the induction as im trying to prove it for $2^{n+1}$ not $2^{n}$? Sorry as you can tell this isnt a strong area of mine, thanks again for the help Oct 31, 2021 at 22:54
• Forward-backward induction of Cauchy? Assume $n$ and prove $n-1$ Oct 31, 2021 at 23:09
• If it exists for $n+1$, it exists for $n$. By the contrapositive and since we know it doesn’t exist for $n$, it doesn’t exist for $n+1$.
– Eric
Oct 31, 2021 at 23:18
• Use induction on $n\ge 3$. Let $n'=n+1$. Show that if $x^{2^n-2}\equiv 1\pmod {2^n}$ whenever $x$ is odd, then $x^{2^{n'}-2}$ $\equiv 1$ $\pmod {2^{n'}}.$ Nov 1, 2021 at 8:39


text:
Measurement of differential cross sections of isolated-photon plus heavy-flavour jet production in pp collisions at s=8 TeV using the ATLAS detector

The ATLAS collaboration

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

15 Цитирования (Scopus)

Аннотация

This Letter presents the measurement of differential cross sections of isolated prompt photons produced in association with a b-jet or a c-jet. These final states provide sensitivity to the heavy-flavour content of the proton and aspects related to the modelling of heavy-flavour quarks in perturbative QCD. The measurement uses proton–proton collision data at a centre-of-mass energy of 8 TeV recorded by the ATLAS detector at the LHC in 2012 corresponding to an integrated luminosity of up to 20.2 fb−1. The differential cross sections are measured for each jet flavour with respect to the transverse energy of the leading photon in two photon pseudorapidity regions: |ηγ|<1.37 and 1.56<|ηγ|<2.37. The measurement covers photon transverse energies 25<ET γ<400 GeV and 25<ET γ<350 GeV respectively for the two |ηγ| regions. For each jet flavour, the ratio of the cross sections in the two |ηγ| regions is also measured. The measurement is corrected for detector effects and compared to leading-order and next-to-leading-order perturbative QCD calculations, based on various treatments and assumptions about the heavy-flavour content of the proton. Overall, the predictions agree well with the measurement, but some deviations are observed at high photon transverse energies. The total uncertainty in the measurement ranges between 13% and 66%, while the central γ+b measurement exhibits the smallest uncertainty, ranging from 13% to 27%, which is comparable to the precision of the theoretical predictions.

Язык оригинала английский 295-317 23 Physics Letters, Section B: Nuclear, Elementary Particle and High-Energy Physics 776 https://doi.org/10.1016/j.physletb.2017.11.054 Опубликовано - 10 янв. 2018

Fingerprint

Подробные сведения о темах исследования «Measurement of differential cross sections of isolated-photon plus heavy-flavour jet production in pp collisions at s=8 TeV using the ATLAS detector». Вместе они формируют уникальный семантический отпечаток (fingerprint).


text:
## Formulae for the Mariner

Format: Paperback

Language: English

Format: PDF / Kindle / ePub

Size: 13.17 MB

The term itself is enshrined in the full title of the Sadleirian Chair, founded (as a professorship) in the mid- nineteenth century. It is an online manuscript submission, review and tracking system. In many field theories it is possible for the dynamical field, a map from spacetime into some manifold, to wrap itself up rather like a high-dimensional knot. Student organisations, such as the Congress of South African Students (COSAS), the South African Students Congress (SASCO) and the South African National Civics Organisation (SANCO), are supported in the development of environmental education initiatives.

## Schaum's Outline of Discrete Mathematics, Revised Third

Format: Print Length

Language: English

Format: PDF / Kindle / ePub

Size: 13.22 MB

Despite this advantage, computer proof assistants haven’t been widely adopted in mainstream mathematics. A comprehensive reference to category theory for students and researchers in mathematics, computer science, logic, cognitive science, linguistics, and philosophy. Both opinions are enjoyable and thought provoking. Model Theory, Commutative Algebra and Algebraic Geometry, Number Theory. I would have been quite lost without that introduction to the material.

## An Introduction to Measure and Probability (Textbooks in

Format: Paperback

Language: English

Format: PDF / Kindle / ePub

Size: 14.16 MB

An excellent treatment of the major logical systems related to foundational study is S. The question of what it means to know mathematically is clearly a part of the larger philosophical question of what it means to know generally. Rosser developed an approach to foundations based on 'function' and 'application of a function to its argument' rather than 'set' and 'a set is an element of another set'. Let me do a couple more example so that you see -- how does a corner evolve? The basics of cryptography, with emphasis on attaining well-defined and practical notions of security.

## Proof of the Incompleteness of Deductive Logic: Second

Format: Print Length

Language: English

Format: PDF / Kindle / ePub

Size: 8.09 MB

In each class I will try to make the discussion self-contained and to give everybody something to take home, regardless of the background. This suggests that the constructive and nonconstructive aspects of mathematics are delicately intertwined and perhaps cannot be strictly separated in any way that isolates and preserves just the constructive part as an undivided whole. The advent of electronic communication and computer technology has widened the appeal of dedicated home working areas, with nearly 20% of all working adults in the United States reporting that they undertake at least some work from home as part of their primary employment.[2]A study is a room in a house which is used for paperwork, computer work, or reading.

## Exercises in Set Theory. Van Nostrand Mathematical Studies

Format: Paperback

Language: English

Format: PDF / Kindle / ePub

Size: 13.16 MB

Journal of Symbolic Logic 21, pp. 280-290. Once thus corrected, König’s theorem became one of the very few results restricting the possible solutions of the continuum problem, implying, e.g., that $$\textit{card}(\mathbf{R})$$ is not equal to $$\aleph_{\omega}$$. They contain, albeit often implicitly, our currently best account of what exists, what we know, and how we know it. The assessment for this course will be via a single take-home paper in April with 2 weeks to complete and submit online.

## An Introduction to Fuzzy Logic for Practical Applications

Format: Paperback

Language: English

Format: PDF / Kindle / ePub

Size: 11.14 MB

Introduction to Statistical Signal Processing, by R. Those implications are especially important in addressing equity concerns, as understanding the level of thinking of the class and the individuals within it, is key in serving the needs of all children. Babinec's approach was that his written explanations were precise. The philosophical message is consistent with my own early experience with mathematics, where I found the boundless reach of its conceptual possibilities invigorating and reassuring.

## Jean Mawhin's contributions to critical point theory

Format: Print Length

Language: English

Format: PDF / Kindle / ePub

Size: 12.06 MB

Yet A and B "have the same form" in that we have reinterpreted only the specific types and relations. Classically the answer is either yes (1), or no (0). Until the mid 1980s, Charles Bell, David Blackwell, A. Jahrbuch der Kurt Gödel Gesellschaft 1989, p.95-97. Without even getting that far, by looking at things very generally, Pauli's principle has an interesting consequence: by so severely restricting the occupation numbers of system energy levels of systems (quantum sets) of Qpoints, the principle implies that that system will not, generally, be able to undergo a condensation phase transition.

## Fuzzy Modeling and Control: Selected Works of Sugeno

Format: Hardcover

Language: English

Format: PDF / Kindle / ePub

Size: 6.17 MB

Several months later I received an email from Roland De Witte of Belgium. The result is a nonnegative integer that is less than 3. The biblical prohibition from eating of the Tree of Life or Tree of Knowledge of Good and Evil may represent another case of a little knowledge being a dangerous thing -- at least to someone's thinking. Our students invariably obtain mathematics-related employment in academic and non-academic settings. CT/9901139, 79 pages, 1999 Structures in higher-dimensional category theory, math.

## Set Theory

Format: Hardcover

Language: English

Format: PDF / Kindle / ePub

Size: 7.95 MB

Maimon, Moses ben: (better known as Maimonides) (Abu Imram Musa Ibn Maimun Ibn Abdallah) (1135-1204) Talmud commentator and leading Jewish philosopher during the Middle Ages. The central thesis of this theory is that every logically consistent mathematical theory necessarily refers to an abstract entity. Separate edition, Paris: Gauthier-Villars, 1977. Nevertheless it is clear that an appeal to the plural interpretation of second-order logic will be tempting for nominalist versions of structuralism.

## Axiomatic Design: Advances and Applications (MIT-Pappalardo

Format: Hardcover

Language: English

Format: PDF / Kindle / ePub

Size: 6.49 MB


text:
# Assessment exercises 4

Exercise 4.1 (9.28 in the book).

Show that there is a formal proof in the first-order language $L$ with non-logical symbols $f , 0 , 1$ (where $f$ is a unary function and $0 , 1$ are constants) of $∃ x ∃ y ( ¬ ( x = u ) ∧ ( f ( x ) = f ( y ) ) )$ from $∀ x ( ( f ( x ) = 0 ) ∨ ( f ( x ) = 1 ) )$ and $∃ x ∃ y ∃ z ( ¬ ( x = y ) ∧ ( ¬ ( y = z ) ∧ ¬ ( z = x ) ) )$.

(Hint: first make an informal argument in the way you might for some other mathematics course you are studying. Then try to tighten up the arguments and write all the cases down. Then rewrite your proof in first order logic.)

Exercise 4.2.

Let $L E$ be the first order language with single non-logical symbol $∼$ (a binary relation).

(a) Write down statements of $L$ saying that $∼$ is an equivalence relation.

(b) Write down a single statement of $L$ saying that there are exactly three $∼$-equivalence classes.

(c) Show how to write down infinitely many statements of $L$ that when taken together say that there are infinitely many $∼$-equivalence classes.

Exercise 4.3.

Let $L G$ be the first order language with a single non-logical symbol $E$ (a binary relation). A simple graph is a nonempty set $V$ of vertices and a set $E$ of unordered pairs of vertices.

(a) Explain how an $L G$-structure might be regarded as a graph, and vice versa. What two extra conditions on $L G$-structures must be true for this graph to be a simple graph?

(b) Write down statements of $L G$ saying that:

(i) the graph is complete (has every possible edge);

(ii) the graph has no cycle of length $n$;

(iii) vertices $x , y$ of $V$ are not connected by any path. (You will need to give infinitely many sentences for this one.)

Exercise 4.4.

A simple graph $( V , E )$ is bipartite if there is a partition $V = V 0 ∪ V 1$ into two disjoint sets such that all edges in $E$ join a vertex in $V 0$ with a vertex in $V 1$. If $G = ( V , E )$ is a simple graph and $∼$ is an equivalence relation on $V$ then we define a graph $G / ∼ = ( V / ∼ , E / ∼ )$ by: for $v ∈ V$ the $∼$-equivalence class of $v$ is denoted $v / ∼$ and $V / ∼$ is the set of $∼$-equivalence classes $v / ∼$ of $V$; and $( v / ∼ , w / ∼ ) ∈ E / ∼$ if and only if $( x , y ) ∈ E$ for some $x ∈ v / ∼$ and $y ∈ w / ∼$. (Note that this construction may create loops, i.e. edges from a vertex to itself, which is also a cycle of length 1.) Suppose $G$ is a simple graph with no cycles of odd length i.e. no sequence of vertices $v 0 , v 1 , … , v 2 k$ with $( v i , v i + 1 ) ∈ E$ for all $i$ and also $( v 2 k , v 0 ) ∈ E$.

(a) Let $X$ be the set of equivalence relations on $V$ such that $G / ∼$ has no cycles of odd length. Show that $X$ is nonempty.

(b) Define $⩽$ on $X$ by letting $∼ 1 ⩽ ∼ 2$ if and only if $x ∼ 1 y$ implies $x ∼ 2 y$ for all $x , y ∈ V$. Show that $( X , ⩽ )$ is a poset with the Zorn property.

(c) Let $∼ ∈ X$ be maximal. Show that $∼$ divides $V$ into either one or two equivalence classes and the case of only one class is only possible is the original graph had no edges. (Hint: two equivalence classes $C , D$ can be merged provided (a) there is no path of odd length between them and (b) provided there is no third class $E$ with paths of from $C$ to $E$ and from $D$ to $E$ of different parity. It follows that any two classes with an even length path between them can be merged, and if two classes cannot be merged but have no path between, then there is another class with an even length path from one of them.)

(d) Deduce that any graph with no odd cycles is bipartite. Prova a converse too, and hence explain how to write down infinitely many sentences of $L G$ saying that a graph is bipartite.


text:
to

### Exact Recovery of Low-rank Tensor Decomposition under Reshuffling

Low-rank tensor decomposition is a promising approach for analysis and understanding of real-world data. Many such analyses require correct recovery of the true latent factors, but the conditions of exact recovery are not known for many existing tensor decomposition methods. In this paper, we derive such conditions for a general class of tensor decomposition methods where each latent tensor component can be reshuffled into a low-rank matrix of arbitrary shape. The reshuffling operation generalizes the traditional unfolding operation, and provides flexibility to recover true latent factors of complex data-structures. We prove that exact recovery can be guaranteed by using a convex program when a type of incoherence measure is upper bounded. The results on image steganography show that our method obtains the state-of-the-art performance. The theoretical analysis in this paper is expected to be useful to derive similar results for other types of tensor-decomposition methods.

### Robust Tensor Recovery using Low-Rank Tensor Ring

Robust tensor completion recoveries the low-rank and sparse parts from its partially observed entries. In this paper, we propose the robust tensor ring completion (RTRC) model and rigorously analyze its exact recovery guarantee via TR-unfolding scheme, and the result is consistent with that of matrix case. We propose the algorithms for tensor ring robust principle component analysis (TRRPCA) and RTCR using the alternating direction method of multipliers (ADMM). The numerical experiment demonstrates that the proposed method outperforms the state-of-the-art ones in terms of recovery accuracy.

### Optimal low rank tensor recovery

We investigate the sample size requirement for exact recovery of a high order tensor of low rank from a subset of its entries. In the Tucker decomposition framework, we show that the Riemannian optimization algorithm with initial value obtained from a spectral method can reconstruct a tensor of size $n\times n \times\cdots \times n$ tensor of ranks $(r,\cdots,r)$ with high probability from as few as $O((r^d+dnr)\log(d))$ entries. In the case of order 3 tensor, the entries can be asymptotically as few as $O(nr)$ for a low rank large tensor. We show the theoretical guarantee condition for the recovery. The analysis relies on the tensor restricted isometry property (tensor RIP) and the curvature of the low rank tensor manifold. Our algorithm is computationally efficient and easy to implement. Numerical results verify that the algorithms are able to recover a low rank tensor from minimum number of measurements. The experiments on hyperspectral images recovery also show that our algorithm is capable of real world signal processing problems.

### On Polynomial Time Methods for Exact Low Rank Tensor Completion

In this paper, we investigate the sample size requirement for exact recovery of a high order tensor of low rank from a subset of its entries. We show that a gradient descent algorithm with initial value obtained from a spectral method can, in particular, reconstruct a ${d\times d\times d}$ tensor of multilinear ranks $(r,r,r)$ with high probability from as few as $O(r^{7/2}d^{3/2}\log^{7/2}d+r^7d\log^6d)$ entries. In the case when the ranks $r=O(1)$, our sample size requirement matches those for nuclear norm minimization (Yuan and Zhang, 2016a), or alternating least squares assuming orthogonal decomposability (Jain and Oh, 2014). Unlike these earlier approaches, however, our method is efficient to compute, easy to implement, and does not impose extra structures on the tensor. Numerical results are presented to further demonstrate the merits of the proposed approach.

### Exact tensor completion using t-SVD

In this paper we focus on the problem of completion of multidimensional arrays (also referred to as tensors) from limited sampling. Our approach is based on a recently proposed tensor-Singular Value Decomposition (t-SVD) [1]. Using this factorization one can derive notion of tensor rank, referred to as the tensor tubal rank, which has optimality properties similar to that of matrix rank derived from SVD. As shown in [2] some multidimensional data, such as panning video sequences exhibit low tensor tubal rank and we look at the problem of completing such data under random sampling of the data cube. We show that by solving a convex optimization problem, which minimizes the tensor nuclear norm obtained as the convex relaxation of tensor tubal rank, one can guarantee recovery with overwhelming probability as long as samples in proportion to the degrees of freedom in t-SVD are observed. In this sense our results are order-wise optimal. The conditions under which this result holds are very similar to the incoherency conditions for the matrix completion, albeit we define incoherency under the algebraic set-up of t-SVD. We show the performance of the algorithm on some real data sets and compare it with other existing approaches based on tensor flattening and Tucker decomposition.


text:
# PCMQtotTol

A - B - C - D - E - F - G - H - I - K - L - M - N - O - P - Q - R - S - T - U - V - W - X

#### PCMQtotTol

Section Hamiltonian::PCM
Type float
Default 0.5

If PCMRenormCharges=.true. and $\delta Q = |[\sum_i q_i| - ((\epsilon-1)/\epsilon)*|Q_M]|>PCMQtotTol$ the polarization charges will be normalized as $q_i^\prime=q_i + signfunction(e, n, \delta Q) (q_i/q_{tot})*\delta Q$ with $q_{tot} = \sum_i q_i$. For values of $\delta Q > 0.5$ (printed by the code in the file pcm/pcm_info.out) even, if polarization charges are renormalized, the calculated results might be inaccurate or erroneous.

Source information

Featured in tutorials