s2fieldsofstudy:
Computer Science
Philosophy

text:
A Dynamic Semantics for Causal Counterfactuals

Under the standard approach to counterfactuals, to determine the meaning of a counterfactual sentence, we consider the “closest” possible world(s) where the antecedent is true, and evaluate the consequent. Building on the standard approach, some researchers have found that the set of worlds to be considered is dependent on context; it evolves with the discourse. Others have focused on how to define the “distance” between possible worlds, using ideas from causal modeling. This paper integrates the two ideas. We present a semantics for counterfactuals that uses a distance measure based on causal laws, that can also change over time. We show how our semantics can be implemented in the Haskell programming language.

Introduction and background
The problem of modeling counterfactual statements and situations has drawn much attention, in computer science, linguistics, and other disciplines. In addition to its intrinsic interest, counterfactual reasoning is important for artificial intelligence systems to be able to handle novel situations (Pearl and Mackenzie, 2018).
The classic approach to counterfactuals in linguistics and philosophy is based on a possible-worlds semantics (Lewis, 1973;Stalnaker, 1968;Kratzer, 1981). To evaluate a counterfactual, we examine a possible world where the antecedent is true, and evaluate the consequent. For example, let us consider the following classic example from Lewis (1973): (1) If kangaroos had no tails, they would topple over.
In the actual world, kangaroos have tails, but we can think of a possible world in which they do not, and consider whether they topple over in that world. However, not all possible worlds should be considered. We can consider a world in which kangaroos have no tails, but use crutches, and perhaps they would not topple over in that world. But in the actual world, kangaroos do not use crutches, so why should we consider those worlds in which they do? We therefore only consider the "closest" possible worlds to the actual world, according to some distance metric or ordering of worlds.
Formally, we have an accessibility relation R, such that R(w, w ) is true if and only if w is sufficiently similar to w. This defines for each world w a context, or modal horizon, consisting of those worlds w such that R(w, w ) (von Fintel, 2001). A counterfactual φ > ψ is true in a world if and only if in all the worlds in the modal horizon where φ is true, ψ is true.
Von Fintel (2001) provides evidence that this context changes over time, by considering sequences of counterfactuals. Briefly, if there are no worlds in the modal horizon where the antecedent φ is true, the modal horizon expands until it includes those φ-worlds most similar to the current world. However, after the counterfactual has been evaluated, the accessibility relation does not revert to its previous state. For example, consider the following sequence of counterfactuals (a Lewis-Sobel sequence): (2) If kangaroos had no tails, they would topple over.
If kangaroos had no tails but used crutches, they would not topple over.
In the closest possible worlds in which kangaroos have no tails, they do not use crutches, and do topple over. However, in the closest worlds in which kangaroos both have no tails and use crutches, they do not topple over. The above sequence makes sense. But the next sequence of counterfactuals, with the order of the sentences reversed (a reverse Sobel sequence), is semantically infelicitous: (3) If kangaroos had no tails but used crutches, they would not topple over.
#If kangaroos had no tails, they would topple over.
The first sentence expands the modal horizon to include worlds in which kangaroos have no tails and use crutches. Once we have introduced worlds in which kangaroos use crutches, we cannot subsequently forget about them when thinking of worlds where they have no tails. Therefore, when evaluating the second sentence, we must consider all worlds in the modal horizon where kangaroos have no tails, including both worlds in which they do and those in which they do not use crutches. In some of these worlds, they topple over, and in others, they do not.
In the classic possible-worlds approach to counterfactuals, the notion of distance or similarity between worlds is deliberately left underspecified. However, a computational implementation of counterfactuals must specify the distance metric to be used. Let us consider a possible world to be characterized by the "facts" true in that world (Kratzer, 1981). Given two worlds that differ from the actual world in the same number of facts, which one is closer? Pollock (1976) suggests that "subjunctive generalizations" are more important than other facts, while Kratzer (1981) suggests that certain facts should be "lumped" together. For example, if one looks in a mirror, one would expect to see their reflection, even if it is not currently visible (because they are not currently looking in the mirror). In other words, the facts "one looks in a mirror" and "one sees their reflection" should be lumped together: if the truth value of one fact changes, the truth of the other should change as well.
A related idea from Pearl (2000) is that the distances between worlds rely on the notion of cause and effect. Specifically, worlds that differ in their causal laws are more distant than worlds whose laws are the same. If we say that looking in a mirror causes one to see their reflection, then among worlds where one looks in the mirror, those in which they see their reflection are closer to the actual world than those where they do not.
Pearl formulates causal laws in terms of structural equations. An equation a = f (b) denotes that, in a particular world, the value of a is dependent on the value of b. This allows us to reason about what the value of a would have been, if the value of b had been different. The set of structural equations, together with an enumeration of the variables, defines a causal model. While Pearl's framework cannot model all possible counterfactual sentences, others have extended the causal modeling approach to different types of counterfactuals (Briggs, 2012).
Causal modeling approaches to counterfactuals make use of interventions: changes in the causal model (Pearl, 2000). Specifically, to evaluate a counterfactual sentence, change the underlying model to make the antecedent true, and allow the change to propagate through the model. Then evaluate the consequent with respect to the new model. Briggs (2012), making connections between causal modeling and possible-worlds approaches, identifies causal models with possible worlds. Applying an intervention then corresponds to selecting the closest possible world where the antecedent is true.
In this paper, we present a semantics for counterfactual sentences that integrates causal reasoning with a dynamic semantics, such as that of Groenendijk and Stokhof (1991). Causal reasoning allows us to give an exact specification of the vague notion of "distance" between worlds, while a dynamic semantics allows us to analyze how the meaning of counterfactuals changes with context. The key idea connecting these two approaches is that causal laws can be encoded in an accessibility relation, and therefore a change in context is equivalent to an intervention in the causal model. We can formalize this using ideas from Alternating-time Temporal Logic with Intentions (ATL+I), a logic for strategic reasoning (Jamroga et al., 2005). We also present a computational implementation of our semantics in the Haskell programming language, available at https://github.com/klai12/dscc.
Our implementation is based on concurrent game structures, introduced by Alur et al. (2002) as an extension of Kripke structures to open (multi-agent) systems. A Kripke structure contains a set of possible worlds, a set of propositions, and a labeling function from worlds to sets of propositions true in those worlds (Kripke, 1963). Concurrent game structures add a set of players, where each player has, for each possible world, a non-empty set of moves available at that world. The transitions available from some world are determined by the moves taken by each player at that world.
We can formally assign types to the above components as follows. We take worlds, propositions, players, and moves to be primitive types World, Prop, Player, and Move, respectively. It will be convenient to also define a type Vector for move vectors, i.e., which move is taken by each player, as [(Player, Move)]. A concurrent game structure then consists of the following six components: We now introduce the notion of a strategy. We adopt the definition in (Jamroga et al., 2005), as a function that, for a given player, maps each world to a non-empty subset of the moves available to that player at that world. Strategies therefore have type World -> [Move]. We can then define a "strategy function" σ as a non-empty subset of the move function, with type Player -> Strategy (or equivalently Player -> World -> [Move]), that specifies a strategy for each player. In ATL+I, because the strategies employed by each player restrict the set of moves from which the player will choose, and the transitions allowed from a world depend on the moves made by each player, the strategy function therefore determines which transitions are allowed. The set of allowed transitions, in turn, forms an accessibility relation that depends on the strategies used by each player.
To return to the setting of counterfactuals, we recall that in a dynamic semantics, the accessibility relation (or modal horizon) changes over time. Furthermore, using a causal modeling approach, the change in the accessibility relation is determined by an intervention in a causal model. Our proposal is to identify variables in a causal model with players in a concurrent game structure. Then we can use the strategy for a player to encode the structural equation for that variable, such that a change in strategy corresponds to an intervention in the causal model.

Example: Kangaroos, tails, and crutches
As an illustrative example, we will again consider the case of the kangaroos. Let us assume that kangaroos will topple over if and only if they have no tails and they do not use crutches; otherwise they will stay upright. Let Q, R, and S be Boolean variables corresponding to whether kangaroos have tails, use crutches, and topple over, respectively. Then we can write the structural equation S = ¬Q ∧ ¬R to encode this causal law. Now we can represent our scenario as a concurrent game structure. First, the set of players in our model is A = {Q, R, S}. Each variable in the causal model is a player in the concurrent game structure. Note that despite the use of the term "player", the players in our model are not agents, or even entities, for that matter; there are no players corresponding to "kangaroos", "tails", or "crutches".
Next we consider the space of possible worlds. We will introduce a possible world for each possible combination of moves the players can make. We will discuss the meanings of the different moves each player can make below; for now, we will say that players Q and R have two moves each (which we will call 0 and 1), and S has three moves (which we will call 0, 1, and x). Therefore, there are 2 × 2 × 3 = 12 possible worlds in our concurrent game structure. We will also say that each player has the same set of available moves at each world; i.e., for all worlds w, the move function D is specified by D(Q, w) = D(R, w) = {0, 1}, and D(S, w) = {0, 1, x}. We will label the possible worlds according to the moves made by each player to arrive at that world; e.g., w 10x is the possible world that results when Q makes move 1, R makes move 0, and S makes move x. The combination {(Q, 1), (R, 0), (S, x)} is then a move vector, and therefore we know that for all worlds w, the transition function δ(w, {(Q, 1), (R, 0), (S, x)}) = w 10x . We can calculate the other values of the transition function in the same way.
We have specified the possible moves for each player at each world, but what do the moves mean? Although our players are not agents in the conventional sense, we can nevertheless think of them as being able to "set" their own values. For all players, then, the move 0 sets its value to 0 in the next world, while 1 sets its value to 1.
The above moves are sufficient for those variables that are exogenous, i.e., those whose values are not dependent on the values of any other variables. In our scenario, Q and R are exogenous variables. For an endogenous variable such as S, whose value is dependent on the values of Q and R, it is not possible to represent the causal law governing S, only using some combination of moves 0 and 1. The reason is because the value of S in the next world is dependent on the values of Q and R in the next world, not the current world. For endogenous variables, therefore, we introduce a third move x, which sets the value of the endogenous variable according to its structural equation. For example, the move x for player S sets the value of S in the next world to be equal to ¬Q ∧ ¬R. In summary, exogenous variables have two moves 0 and 1, while endogenous variables have a third move x.
The initial set of propositions is P = {q, r, s}. Our propositions correspond to valuations of each of the variables; e.g., q is true in those worlds where the value of Q is 1, etc. Where necessary, the values of endogenous variables can be calculated using their structural equations. For example, the value of S in w 10x is ¬1 ∧ ¬0 = 0 ∧ 1 = 0. The labeling function is then straightforward to calculate: L(w 000 ) = ∅, L(w 10x ) = {q}, etc.
Finally, we must specify our initial conditions: the initial strategies of each player. For player S, the strategy is to enforce the causal law S = ¬Q ∧ ¬R at each world. Therefore the strategy for S is simply λw.x: at all worlds w, make move x.
As for players Q and R, because they are exogenous variables, they do not have structural equations in Pearl's causal models (Pearl, 2000). However, we do not want to say that they have no strategies. As previously mentioned, when evaluating a counterfactual sentence, we only want to consider those worlds that are closest to the actual world. But in ATL+I, having no strategy means placing no restrictions on which worlds are accessible from the actual world (Jamroga et al., 2005). Intuitively, given a world with some value of Q, worlds with the same value of Q can be considered closer to that world than worlds with the opposite value, all else being equal. Therefore, one possible strategy is to keep the value of Q the same: The strategy for R can be similarly specified.

The dynamics of causal counterfactuals
Now we can describe the evaluation of counterfactual sentences in our framework. We translate sentences into formulas of type Form. In addition to the formulas of propositional and basic modal logic, we also include the formula scheme Str a strategy phi; these correspond to ATL+I sentences (str a σ a )φ.
In ATL+I, it is the evaluation of str-formulas in which changes of strategy occur; in our framework, counterfactual sentences are translated into str-formulas for evaluation.
Formulas must of course be evaluated relative to some model. In addition, in a dynamic semantics, we must also keep track of the context. To do this, we make use of Haskell's state monad. We define the type Model of our states as a record type, that includes the current strategy function, as well as four components of our concurrent game structure: the sets of players and worlds, and the labeling and transition functions. Because of how we constructed our concurrent game structures above, the set of propositions and the move function can be inferred from the other components.
For a given function (and context), our model checker returns the set of possible worlds where the formula is true. As such, our main function, check, has type Form -> State Model [World]. The model checker is based heavily on that in (Jamroga et al., 2005) for ATL+I, which itself is derived from the model checker for ATL in (Alur et al., 2002). Propositions are checked using the labeling function, and formulas of propositional logic follow via the usual set-theoretic operations. The checking of modal formulas makes use of a pre-image function, which, given a set of possible worlds, returns the set of worlds that can access any of those worlds. Then, for example, to check a formula ♦φ, we first find the set of worlds where φ is true, and then calculate the set of worlds such that the φ-worlds are accessible.
Finally, to check str-formulas, we introduce a revise function. This is the mechanism by which causal interventions are modeled. Formally, let σ be the current strategy for player a, and σ be a's new strategy. Then we can say that revise(a, σ ) = {σ ∪ σ }.
We should note that our revise function differs from that of Jamroga et al. (2005). Whereas changes of strategy in ATL+I involve replacement of the player's previous strategy, our revise function simply add the moves from σ to a's previous strategy. We recall that in von Fintel's dynamic account of counterfactuals, the accessibility relation (modal horizon) expands but does not contract. In other words, all worlds accessible from a given world before an update to the model, remain accessible afterwards.
Returning to the kangaroos, we can now see the difference in the evaluation of the Lewis-Sobel sequence in (2) and the reverse Sobel sequence in (3). We will use the propositions q, r, and s as before, to represent kangaroos having tails, using crutches, and toppling over, respectively. In evaluating the sentence "If kangaroos had no tails, they would topple over" under the causal modeling approach, we apply an intervention in the model to set Q = 0. This corresponds to a strategy for Q to go to a world where ¬q is true; i.e., λw.0. Then, following von Fintel (2001), we check whether in all accessible worlds where ¬q is true, s is also true; this is the strict conditional (¬q → s). Therefore, the formula we want to evaluate is (str Q (λw.0)) (¬q → s).
Similarly, when we evaluate the sentence "If kangaroos had no tails but used crutches, they would not topple over", we want to expand our modal horizon to include worlds where ¬q and r are both true. This involves changes in strategy by both Q and R; Q to set Q = 0, R to set R = 1. The formula to be evaluated must therefore include both an (str Q (λw.0)) term and an (str R (λw.1)) term. Then, since we want to check the truth of ¬s in those accessible worlds where both ¬q and r are true, our formula is (str Q (λw.0))(str R (λw.1)) ((¬q ∧ r) → ¬s).
Suppose that starting from our initial conditions, the sentence "If kangaroos had no tails, they would topple over" is uttered. We first update the strategy function for Q, to add the move 0 to Q's initial strategy. This has no effect in worlds where Q = 0, as the default strategy for Q is to keep its value the same. However, in worlds where Q = 1, Q now has two moves consistent with its new strategy, 0 and 1. Now, using the updated accessibility relation, we evaluate the formula (¬q → s). Every world now has an accessible ¬q-world. We note that according to the structural equation S = ¬Q ∧ ¬R, s will be true in those worlds where ¬q and ¬r hold. Since S's strategy is to enforce the structural equation, we know that it will hold in all accessible worlds. In addition, R's strategy continues to dictate that from every world, any accessible world will have the same valuation of R. We conclude that the sentence is true in those worlds where R = 0; these include the actual world w 10x .
Then suppose the sentence "If kangaroos had no tails but used crutches, they would not topple over" is uttered. Again, we update the strategy function for Q to add move 0. But since 0 was previously added when evaluating the first sentence, this revision has no effect. Next, we add the move 1 to all worlds in R's strategy, similarly as before. Now we evaluate the strict conditional ((¬q ∧ r) → ¬s). Since S's strategy still has not changed, the causal law S = ¬Q ∧ ¬R continues to hold in every accessible world. Therefore, for every world in our model, in every accessible world where (¬q ∧ r) is true, ¬s is true, and so is the sentence.
What if the order of the two sentences were reversed? First, starting again from the initial conditions, the sentence "If kangaroos had no tails but used crutches, they would not topple over" is uttered. Because move 0 had not been added yet, it is this sentence that adds 0 to Q's strategy. All other effects of uttering this sentence are the same as before, as is the set of possible worlds where it is true. However, we can see a difference in the evaluation of the second sentence "If kangaroos had no tails, they would topple over". Updating the strategy function for Q has no effect, since the move 0 has already been added to Q's strategy by the first sentence. Furthermore, it is no longer the case that R's strategy keeps the valuation of R constant; as a result of the first sentence, move 1 is now available to R at every world. In other words, among the ¬q-worlds accessible from any given world, one of them will also be an r-world. Since S = ¬Q ∧ ¬R holds in every world, we know that from any world, one of the accessible ¬q-worlds will not be an s-world. We conclude that the sentence does not hold in any world.

Translating counterfactual sentences into str-formulas
One challenge in synthesizing a causal modeling approach to counterfactuals with a possible-worlds semantics is the difference in how counterfactual sentences are evaluated in the two approaches. Under the classic possible-worlds framework, we check whether in the closest possible worlds where the antecedent is true (making any changes to the accessibility relation, if necessary, to ensure that at least one such possible world exists), the consequent is true. In a causal theory of counterfactuals, the antecedent of the counterfactual determines the intervention to be applied to the causal model. Then, the consequent is evaluated relative to the new model.
In this paper, we identified the necessary change in the accessibility relation with the intervention in the causal model, which we implement as a change in strategy for some player. Such an approach raises two questions. The first question concerns which possible worlds count as worlds where the antecedent is true. In the kangaroo example, when we translated a counterfactual of the form φ > ψ into an strformula, the strict conditional portion of the formula was simply (φ → ψ). In other words, if the antecedent of the counterfactual is φ, then we check whether the accessible φ-worlds are also ψ-worlds. However, there is evidence that this approach may not work for all scenarios. Briggs (2012) discusses the scenario, originally found in Pearl (2000), of an execution of a prisoner. A full description of the scenario can be found in either of the above papers; we note here that there are two executioners, X and Y, and whether they fire is determined by whether the captain C signals for them to do so. In other words, the behavior of executioner X is governed by the structural equation X = C. If either executioner fires, the prisoner dies. In the actual world, the captain signals, both executioners fire, and the prisoner dies.
Briggs considers the sentence "If executioner X had fired, then (even) if the captain had not signalled, the prisoner would have died." Under a causal model, we intervene to change the structural equation X = C to X = 1. However, in the classic possible-worlds framework, no change in the accessibility relation is necessary. Executioner X fires in the actual world, and as a consequence of (weak) centering, the assumption that every world is at least as similar to itself as to any other world, every world is then accessible to itself. Under the classic approach, we check the truth of the consequent in the closest possible world where the antecedent is true; i.e., the actual world, where the consequent is false. But as Briggs notes, applying the intervention to the causal model changes the truth of the consequent.
When specifying a set of possible worlds corresponding to a causal model, we must distinguish between worlds where different causal laws hold. For example, in the kangaroo scenario, we distinguish worlds w 10x (where kangaroos do not topple over because they have tails) and w 100 (where they do not topple over, because it is a law of nature that they never topple over), even though the same propositions are true in both worlds: L(w 100 ) = L(w 10x ) = {q}. Likewise, the antecedent of the counterfactual in the execution case is the proposition that executioner X fires; let us call it x. We note that x does not determine what structural equation holds in a particular world; in some x-worlds, the relevant causal law is X = 1, while in others, it is X = C. When we say "if executioner X had fired" in a causal model, the relevant possible worlds are those in which the structural equation is X = 1. The corresponding proposition is not x, but a different proposition (call it x 1 ), which is true in exactly those worlds where the causal law X = 1 holds.

Counterfactuals with complex antecedents
Second, we note that antecedents of counterfactuals are propositions (of type Prop), while strategies have type World -> [Move]. Is there a way to systematically translate propositions into strategies? We have already seen that for atomic propositions such as r, we intervene to make sure that there is an accessible world where r is true, by adding the move 1 to the strategy of player R at every world: λw.1. Similarly, for negations of atomic propositions, such as ¬q, we add move 0 to Q's strategy: λw.0.
We have also seen an example of a conjunction, (¬q ∧ r). To ensure that there is an accessible world where the conjunction holds, we simply have both players change their strategies in sequence: (str Q (λw.0))(str R (λw.1)).... We note that the order each player changes their strategy does not matter. The moves each player is allowed to make are affected only by their own strategy, not those of any other players, and the strict conditional portion of the counterfactual formula is only evaluated after all strategy changes.
For other complex antecedents, Briggs (2012) borrows the idea of a state space from Fine (2012). States are defined by a valuation of some variable(s); e.g., Q = 0 ∧ R = 1. For propositional antecedents (including negations, conjunctions, disjunctions, and material conditionals), Briggs specifies states that make the antecedent true. For example, a disjunctive antecedent (φ ∨ ψ) is made true by three states or interventions: one that sets φ = 1, one that sets ψ = 1, and one that sets both φ = 1 ∧ ψ = 1.
One challenge that arises in adapting this approach to ours is that evaluating the disjunction involves checking the results of three different interventions applied to the original model. However, in our dynamic semantics, once an intervention is made, the moves added to the player's strategy remain available to future evaluations; there is no "going back" to try a different intervention. In addition, while the states associated with the disjunction (φ ∨ ψ) are the same as those associated with the negated conjunction ¬(¬φ ∧ ¬ψ), Ciardelli et al. (2018) provide evidence that those antecedents in fact have different meanings.
Furthermore, it is not clear what impact, if any, a disjunctive antecedent should have on the accessibility relation at all. Ciardelli et al. (2018) discuss the example of two switches for a light. They are connected in such a way that the light is on if the switches are both up or both down, and off otherwise. In the actual world, the switches are both up and the light is on. While Ciardelli et al. do not consider sequences of counterfactuals, it is easy enough to construct a reverse Sobel sequence as with the kangaroos: (4) If switch A and switch B were both down, the light would be on.
#If switch A was down, the light would be off. Now let us replace the conjunction with a disjunction. In their experiment, Ciardelli et al. found that the sentence "If switch A or switch B was down, the light would be off." was judged by most participants to be true (in contrast with the sentence "If switch A and switch B were not both up, the light would be off.", with a negated conjunctive antecedent). If we use this sentence instead in our sequence, the infelicity seems to go away: (5) If switch A or switch B was down, the light would be off.
If switch A was down, the light would be off.
In fact, according to the rule of simplification of disjunctive antecedents, the second sentence is a logical consequence of the first. Nevertheless, this indicates that perhaps the modal horizon did not expand to include worlds where switch B was down in this case, at least not permanently; if it had, then we would have to consider them when evaluating the second sentence. Alternatively, von Fintel (2001) suggests that logical arguments, unlike normal discourse, carry with them an assumption of constant context. Certainly more research is needed in this area.

Conclusion
In this paper, we present a semantics for counterfactuals that combines ideas from dynamic semantics and causal modeling approaches. Our implementation is based on concurrent game structures, where variables are interpreted as players and interventions as changes in players' strategies. Using the classic example of kangaroos with no tails, we show how our approach is able to capture judgments about sequences of counterfactuals.


extfieldsofstudy:
Computer Science
Engineering

text:
Improvements of computational ghost imaging by using Special-Hadamard patterns

We introduced a new kind of patterns named Special-Hadamard patterns, which could be used as structured illuminations of computational ghost imaging. Special-Hadamard patterns can get a better image quality than Hadamard patterns in a noisy environment. We can completely reconstruct the original object in a noiseless environment by using Special-Hadamard patterns, and the size of object also can be adjusted arbitrarily, these advantages cannot be achieved by other common patterns. We also performed simulations to compare the results of Special Hadamard patterns with the results of Hadamard patterns. We found Special Hadamard patterns can greatly improve the image quality of computational ghost imaging.

In CGI, researchers usually use a projector to generate structured patterns, and it is found that random binary patterns can get excellent imaging quality in experiment. Hadamard pattern is a special binary pattern. Hadamard pattern computational ghost imaging (HCGI) has significant advantages over random binary patterns in CGI system. It can be reconstructed from the original image almost completely without algorithm noise. HCGI also has strong robustness with less number of measurements. Hadamard pattern is used extensively in experiments and lots of papers related to Hadamard patterns has been published recently [21,22].
However, HCGI has some drawbacks which restricting image quality and application range. In this paper, we investigate the causes of these drawbacks. And then we introduce a new kind of patterns Special-Hadamard patterns to solve these problems. We evaluate the result of Special-Hadamard matrix computational ghost imaging (SHCGI). We also compared the numerical simulations of HCGI and SHCGI. The reconstracted image quality is improved by using Special-Hadamard patterns, and these patterns are more universal than Hadamard patterns. Hadamard matrix (H) is a square matrix whose entries are either +1 or −1 and whose rows and columns are mutually orthogonal independently. Then it has some special properties for an N-dimensional Hadamard matrix, HH T = N I (I is the identity matrix). N is strictly limited by Hadamard matrix, Here, i is a positive integer. We generate Hadamard matrix by computer directly in daily experiment. In CGI system, we denote Hadamard matrix as And we project the nth known pattern which is gained from reshaping H n . For simplification, we use a vector-matrix notation with N 1 × N 2 images given as vectors in T with dimension N (N = N 1 N 2 ), we denote T as Fig.1 presents the schematic of a typical CGI system with Hadamard patterns.
The second-order correlation function of HCGI can be written as where B n is the light intensity signal corresponding the nth pattern from the bucket sensor, and B n can be written as According to Eqs. (4) and (5), the second-order correlation function can be written as From the definition of Hadamard matrix, we can get HH T = N I, where I is the identity matrix, and then that means the original image can be completely reconstructed. Because the item "−1" cannot be illuminated by the projector in experiment, we need to transform "−1" into "0" of Hadamard matrix by the function Here, we call H pseudo-Hadamard matrix. For HCGI, we use the H matrix to reconstruct the imaging, and we find that According to Eq. (6), for an ideal noiseless environment, the reconstructed image G of HCGI can be written as If we want to reconstruct the original imaging completely, a relationship needs to be satisfied between G and T, According to the Eq. (10), we can find the first pixel is bigger than others, and G cannot satisfy this relationship of Eq. (11). Thus we cannot get the same reconstructed image as the original. The reconstructed result G is manully revised, removing the first error pixel to reconstruct the rest of this image. And for the remaining pixels, Eq. (11) can be partly satisfied.
If we consider the system without the first pixel of HCGI, we give the constructed image of pseudo-Hadamard patterns and random binary patterns of CGI in Fig. 2, when the system has noise. Here, we use mean square error (MSE) to descibe the image quality, where here G max is the maximal value of all the G (except the first pixel), and G min is the minimal value of all the G. We find that the number of measurements are the same, the constructed image of pseudo-Hadamard patterns of CGI is better than random binary pattern of CGI. But, the number of measurements is fixed. When the number of measurements is increasing, the reconstructed image quality from random binary pattern is better than pseudo-Hadamard pattern, which means the number of measurements is very important. We introduce a new kind of patterns Special-Hadamard patterns. Fig. 3 show the procedure of generating Special-Hadamard patterns. We first generate a K × K pseudo-  Hadamard matrix ( H) and remove the first row of H, then random extract N rows from the remaining matrix to make up an N × K Special Hadamard matrix (S). Finally, we reshape each column into projected pattern. We also need to ensure that the number of independent columns of Special Hadamard matrix is more than N, otherwise incomplete image will be produced because of insufficient information.
We can easily derive the characteristic of S from the characteristic of H. For an N × K Special Hadamard matrix S, we can get Then, in a noiseless environment, the reconstructed image G of SHCGI can be written as that means the image can be reconstructed completely according to Eq. (11). The column length of Special Hadamard matrix (N) is arbitrary (N < K) for SHCGI, that means we can reconstruct from the original image that the number of pixels can be arbitrary. And for HCGI, the number of pixels is in set A. As shown in Fig. 4, we reconstruct from the image which has 30000 binary transimitive pixels with 32768 Special Hadamard patterns.
We have discussed that the number of measurements is very significant to the quality of reconstructed image. SHCGI break the limitation of measurement times of HCGI, then we can reconstruct from the original object with far more patterns. The number of Special Hadamard patterns (K) can be increased to infinity and is in set A. We perform numerical simuliations to study the relationship between MSE and the number of measurements. In this experiment, the original object has 4096 binary transimitive pixels, thus HCGI only has 4096 patterns. It is found that the the quality of reconstructed images are greatly improved, as shown in Fig. 5, when the number of measurements is increased.
We also perform numerical simulations to compare SHCGI results with HCGI results, as shown in Fig. 6. The original object has 4096 binary transimitive pixels. In a noiseless environment, we can find HCGI cannot reconstruct from the original image in Fig. 6 (a), and HCGI can restore successfully after manully revising the first pixel in Fig. 6 (b). And SHCGI can reconstruct image completely from MSE = 0 in Fig. 6 (c) and (d). In a noisy environment, the results are reconstructed from 4096 patterns, 5120 patterns and 32768 patterns, as shown in Fig. 6 (f)-(h) respectively. It is very clear that the image quality are improved when patterns are increased, that means SHCGI has more powerful robustness than HCGI.
To sum it all up, we analysed the drawbacks of restricting the reconstructed image quality in Hadamard pattern computational ghost imaging (HCGI). Then we introduced a new kind of patterns Special-Hadamard patterns, which are used as the structured illumination of computational ghost imaging. Special Hadamard patterns are generated from Hadamard matrix. But Special Hadamard pattern computational ghost imaging (SHCGI) break the HCGI limitations on the number of measurements (K) and the number of pixels (N). In SHCGI system, K can be increased to infinity (K ∈ A) and the total number of pixels (N) is arbitrary integer(N ≤ K − 1), and that means SHCGI has more powerful robustness and wider range of applications than HCGI. SHCGI also can avoid the abnormal point which is founded at the first pixel of HCGI result, that means SHCGI can reconstruct the original image completely in a noiseless environment. In simulation, we compared SHCGI results with HCGI results using mean square error, showed that SHCGI can greatly improve the image quality of computational ghost imaging. We suppose that these improvements will be helpful in practical applications.


extfieldsofstudy:
Mathematics
Computer Science

text:
Nonparametric regression using needlet kernels for spherical data

Needlets have been recognized as state-of-the-art tools to tackle spherical data, due to their excellent localization properties in both spacial and frequency domains. This paper considers developing kernel methods associated with the needlet kernel for nonparametric regression problems whose predictor variables are defined on a sphere. Due to the localization property in the frequency domain, we prove that the regularization parameter of the kernel ridge regression associated with the needlet kernel can decrease arbitrarily fast. A natural consequence is that the regularization term for the kernel ridge regression is not necessary in the sense of rate optimality. Based on the excellent localization property in the spacial domain further, we also prove that all the $l^{q}$ $(01\leq q<\infty)$ kernel regularization estimates associated with the needlet kernel, including the kernel lasso estimate and the kernel bridge estimate, possess almost the same generalization capability for a large range of regularization parameters in the sense of rate optimality. This finding tentatively reveals that, if the needlet kernel is utilized, then the choice of $q$ might not have a strong impact in terms of the generalization capability in some modeling contexts. From this perspective, $q$ can be arbitrarily specified, or specified merely by other no generalization criteria like smoothness, computational complexity, sparsity, etc..

1. Introduction. Contemporary scientific investigations frequently encounter a common issue of exploring the relationship between a response variable and a number of predictor variables whose domain is the surface of a sphere. Examples include the study of gravitational phenomenon [12], cosmic microwave background radiation [10], tectonic plat geology [6] and image rendering [31]. As the sphere is topologically a compact two-point homogeneous manifold, some widely used schemes for the Euclidean space such as the neural networks [13] and support vector machines [27] are no more the most appropriate methods for tackling spherical data. Designing efficient and exclusive approaches to extract useful information from spherical data has been a recent focus in statistical learning [11,18,23,26].
Recent years have witnessed a considerable approaches about nonparametric regression for spherical data. A classical and long-standing technique is the orthogonal series methods associated with spherical harmonics [1], with which the local performance of the estimate are quite poor, since spherical harmonics are not well localized but spread out all over the sphere. Another widely used technique is the stereographic projection methods [11], in which the statistical problems on the sphere were formulated in the Euclidean space by use of a stereographic projection. A major problem is that the stereographic projection usually leads to a distorted theoretical analysis paradigm and a relatively sophisticate statistical behavior. Localization methods, such as the Nadaraya-Watson-like estimate [26], local polynomial estimate [3] and local linear estimate [18] are also alternate and interesting nonparametric approaches. Unfortunately, the manifold structure of the sphere is not well taken into account in these approaches. Mihn [21] also developed a general theory of reproducing kernel Hilbert space on the sphere and advocated to utilize the kernel methods to tackle spherical data. However, for some popular kernels such as the Gaussian [22] and polynomials [5], kernel methods suffer from either a similar problem as the localization methods, or a similar drawback as the orthogonal series methods. In fact, it remains open that whether there is an exclusive kernel for spherical data such that both the manifold structure of the sphere and localization requirement are sufficiently considered.
Our focus in this paper is not on developing a novel technique to cope with spherical nonparametric regression problems, but on introducing an exclusive kernel for kernel methods. To be detailed, we aim to find a kernel that possesses excellent spacial localization property and makes fully use of the manifold structure of the sphere. Recalling that one of the most important factors to embody the manifold structure is the special frequency domain of the sphere, a kernel which can control the frequency domain freely is preferable. Thus, the kernel we need is actually a function that possesses excellent localization properties, both in spacial and frequency domains. Under this circumstance, the needlet kernel comes into our sights. Needlets, introduced by Narcowich et al. [24,25], are a new kind of second-generation spherical wavelets, which can be shown to make up a tight frame with both perfect spacial and frequency localization properties. Furthermore, needlets have a clear statistical nature [2,14], the most important of which is that in the Gaussian and isotropic random fields, the random spherical needlets behave asymptotically as an i.i.d. array [2]. It can be found in [24] that the spherical needlets correspond a needlet kernel, which is also well localized in the spacial and frequency domains. Consequently, the needlet kernel is proved to possess the reproducing property [24,Lemma 3.8], compressible property [24,Theorem 3.7] and best approximation property [24,Corollary 3.10].
The aim of the present article is to pursue the theoretical advantages of the needlet kernel in kernel methods for spherical nonparametric regression problems. If the kernel ridge regression (KRR) associated with the needlet kernel is employed, the model selection then boils down to determining the frequency and regularization parameter. Due to the excellent localization in the frequency domain, we find that the regularization parameter of KRR can decrease arbitrarily fast for a suitable frequency. An extreme case is that the regularization term is not necessary for KRR in the sense of rate optimality. This attribution is totally different from other kernels without good localization property in the frequency domain [8], such as the Gaussian [22] and Abel-Poisson [12] kernels. We attribute the above property as the first feature of the needlet kernel. Besides the good generalization capability, some real world applications also require the estimate to possess the smoothness, low computational complexity and sparsity [27]. This guides us to consider the l q (0 < q < ∞) kernel regularization (KRS) schemes associated with the needlet kernel, including the kernel bridge regression and kernel lasso estimate [32]. The first feature of the needlet kernel implies that the generalization capability of all l q -KRS with 0 < q < ∞ are almost the same, provided the regularization parameter is set to be small enough. However, such a setting makes there be no difference among all l q -KRS with 0 < q < ∞, as each of them behaves similar as the least squares. To distinguish different behaviors of the l q -KRS, we should establish a similar result for a large regularization parameter. By the aid of a probabilistic cubature formula and the the excellent localization property in both frequency and spacial domain of the needlet kernel, we find that all l q -KRS with 0 < q < ∞ can attain almost the same optimal generalization error bounds, provided the regularization parameter is not larger than O(m q−1 ε). Here m is the number of samples and ε is the prediction accuracy. This implies that the choice of q does not have a strong impact in terms of the generalization capability for l q -KRS, with relatively large regularization parameters depending on q. From this perspective, q can be specified by other no generalization criteria like smoothness, computational complexity and sparsity. We consider it as the other feature of the needlet kernel.
The reminder of the paper is organized as follows. In the next section, the needlet kernel together with its important properties such as the reproducing property, compressible property and best approximation property is introduced. In Section 3, we study the generalization capability of the kernel ridge regression associated with the needlet kernel. In Section 4, we consider the generalization capability of the l q kernel regularization schemes, including the kernel bridge regression and kernel lasso. In Section 5, we provide the proofs of the main results. We conclude the paper with some useful remarks in the last section.
2. The needlet kernel. Let S d be the unit sphere embedded into R d+1 . For integer k ≥ 0, the restriction to S d of a homogeneous harmonic polynomial of degree k on the unit sphere is called a spherical harmonic of degree k. The class of all spherical harmonics of degree k is denoted by H d k , and the class of all spherical harmonics of degree k ≤ n is denoted by Π d n . Of course, Π d n = n k=0 H d k , and it comprises the restriction to S d of all algebraic polynomials in d + 1 variables of total degree not exceeding n. The dimension of H d k is given by n ∼ n d . The addition formula establishes a connection between spherical harnomics of degree k and the Legendre polynomial P d+1 k [12]: where P d+1 k is the Legendre polynomial with degree k and dimension d + 1. The Legendre polynomial P d+1 k can be normalized such that P d+1 k (1) = 1, and satisfies the orthogonality relations where δ k,j is the usual Kronecker symbol.
The following Funk-Hecke formula establishes a connection between spherical harmonics and function φ ∈ L 1 ([−1, 1]) [12] (2.2) A function η is said to be admissible [25] if η ∈ C ∞ [0, ∞) satisfies the following condition: suppη ⊂ [0, 2], η(t) = 1 on [0, 1], and 0 ≤ η(t) ≤ 1 on [1,2]. The needlet kernel [24] is then defined to be The needlets can be deduced from the needlet kernel and a spherical cubature formula [4]. We refer the readers to [2,14,24] for a detailed description of the needlets. According to the definition of the admissible function, it is easy to see that K n possess excellent localization property in the frequency domain. The following Lemma 2.1 that can be found in [24] and [4] yields that K n also possesses perfect spacial localization property. Lemma 2.1. Let η be admissible. Then for every k > 0 and r ≥ 0 there exists a constant C depending only on k, r, d and η such that We also denote by E N (f ) p the best approximation error of Then the needlet kernel K n satisfies the following Lemma 2.2, which can be deduced from [24]. Lemma 2.2. K n is a reproducing kernel for Π d n , that is K n * P = P for P ∈ Π d n . Moreover, for any f ∈ L p (S d ), 1 ≤ p ≤ ∞, we have K n * f ∈ Π d 2n , and where C is a constant depending only on d, p and η. It is obvious that K n is a semi-positive definite kernel, thus it follows from the known Mercer theorem [21] that K n corresponds a reproducing kernel Hilbert space (RKHS), H K . Lemma 2.3. Let K n be defined above, then the reproducing kernel Hilbert space associated with K n is the space Π d 2n with the inner product: 3. Kernel ridge regression associated with the needlet kernel. In spherical nonparametric regression problems with predictor variables X ∈ X = S d and a real response variable Y ∈ Y ⊆ R, we observe m i.i.d. samples z m = {(x 1 , y 1 ), . . . , (x m , y m )} from an unknown distribution ρ. Without loss of generality, it is always assumed that which is minimized by the regression function [13] defined by We formulate the learning problem in terms of probability estimates rather than expectation estimates. To this end, we present a formal way to measure the performance of learning schemes in probability. Let Θ ⊂ L 2 ρX and M(Θ) be the class of all Borel measures ρ such that f ρ ∈ Θ. For each ε > 0, we enter into a competition over all estimators based on m samples Φ m : As it is impossible to obtain a nontrivial convergence rate wtihout imposing any restriction on the distribution ρ [13, Chap.3], we should introduce certain prior information. Let µ ≥ 0. Denote the Bessel-potential Sobolev class W r [20] to be all f such that It follows from the well known Sobolev embedding theorem that W r ⊂ C(S d ), provided r > d/2. In our analysis, we assume f ρ ∈ W r .
The learning scheme employed in this section is the following kernel ridge regression (KRR) associated with the needlet kernel where π M u := min{M, |u|}sgn(u) is the truncation operator. As there isn't any additional computation for employing the truncation operator, the truncation operator has been used in large amount of papers, to just name a few, [5,9,13,15,21,32,33]. The following Theorem 3.1 illustrates the generalization capability of KRR associated with the needlet kernel and reveals the first feature of the needlet kernel.
Theorem 3.1. Let f ρ ∈ W r with r > d/2, m ∈ N, ε > 0 be any real number, and n ∼ ε −r/d . If f z,λ is defined as in (3.2) with 0 ≤ λ ≤ M −2 ε, then there exist positive constants C i , i = 1, . . . , 4, depending only on M , ρ, and d, ε 0 > 0 and ε − , ε + satisfying such that for any ε < ε − , and for any ε ≥ ε + , We give several remarks on Theorem 3.1 below. In some real world applications, there are only m data available, and the purpose of learning is to produce an estimate with the prediction error at most ε and statisticians are required to assess the probability of success. It is obvious that the probability depends heavily on m and ε. If m is too small, then there isn't any estimate that can finish the learning task with small ε. This fact is quantitatively verified by the inequality (3.4). More specifically, (3.4) shows that if the learning task is to yield an accuracy at most ε ≤ ε − , and other than the prior knowledge, f ρ ∈ W r , there are only m ≤ ε −(2r+d)/(2r) − data available, then all learning schemes, including KRR associated with the needlet kernel, may fail with high probability. To circumvent it, the only way is to acquire more samples, just as inequalities (3.5) purport to show. (3.5) says that if the number of samples achieves ε −(2r+d)/(2r) + , then the probability of success of KRR is at least 1 − e −C4mε . The first inequality (lower bound) of (3.5) implies that this confidence can not be improved further. The values of ε − and ε + thus are very critical since the smallest number of samples to finish the learning task lies in the interval [ε − , ε + ]. Inequalities (3.3) depicts that, for KRR, there holds This implies that the interval [ε − , ε + ] is almost the shortest one in the sense that up to a logarithmic factor, the upper bound and lower bound of the interval are asymptotically identical. Furthermore, Theorem 3.1 also presents a sharp phase transition phenomenon of KRR. The behavior of the confidence function changes dramatically within the critical interval [ε − , ε + ]. It drops from a constant ε 0 to an exponentially small quantity. All the above assertions show that the learning performance of KRR is essentially revealed in Theorem 3.1.
An interesting finding in Theorem 3.1 is that the regularization parameter of KRR can decrease arbitrarily fast, provided it is smaller than M −2 ε. The extreme case is that the least-squares possess the same generalization performance as KRR. It is not surprised in the realm of nonparametric regression, due to the needlet kernel's localization property in the frequency domain. Via controlling the frequency of the needlet kernel, H K is essentially a linear space with finite dimension. Thus, [13, Th.3.2& Th.11.3] together with Lemma 5.1 in the present paper automatically yields the optimal learning rate of the least squares associated with the needlet kernel in the sense of expectation. Differently, Theorem 3.1 presents an exponential confidence estimate for KRR, which together with (3.3) makes [13,Th.11.3] be a corollary of Theorem 3.1. Theorem 3.1 also shows that the purpose of introducing regularization term in KRR is only to conquer the singular problem of the kernel matrix, A : n in our setting. Under this circumstance, a small λ leads to the ill-condition of the matrix A + mλI and a large λ conducts large approximation error. Theorem 3.1 illustrates that if the needlet kernel is employed, then we can set λ = M −2 ε to guarantee both the small condition number of the kernel matrix and almost generalization error bound. From (3.3), it is easy to deduce that to attain the optimal learning rate m −2r/(2r+d) , the minimal eigenvalue of the matrix A + mλI is m d/(2r+d) , which can guarantee that the matrix inverse technique is suitable to solve (3.2).
4. l q kernel regularization schemes associated with the needlet kernel. In the last section, we analyze the generalization capability of KRR associated with the needlet kernel. This section aims to study the learning capability of the l q kernel regularization schemes (KRS) whose hypothesis space is the sample dependent hypothesis space [32] associated with K n (·, ·) , The corresponding l q -KRS is defined by where With different choices of the order q, (4.1) leads to various specific forms of the l q regularizer. f z,λ,2 corresponds to the kernel ridge regression [27], which smoothly shrinks the coefficients toward zero and f z,λ,1 leads to the LASSO [30], which sets small coefficients exactly at zero and thereby also serves as a variable selection operator. The varying forms and properties of f z,λ,q make the choice of order q crucial in applications. Apparently, an optimal q may depend on many factors such as the learning algorithms, the purposes of studies and so forth. The following Theorem 4.1 shows that if the needlet kernel is utilized in l q -KRS, then q may not have an important impact in the generalization capability for a large range of regularization parameter in the sense of rate optimality.
Theorem 4.1. Let f ρ ∈ W r with r > d/2, m ∈ N, ε > 0 be any real number, and n ∼ ε −r/d . If f z,λ,q is defined as in (4.1) with λ ≤ m −1 ε and 0 < q < ∞, then there exist positive constants C i , i = 1, . . . , 4, depending only on M , ρ, q and d, ε 0 > 0 and ε − m , ε + m satisfying such that for any ε < ε − m , and for any ε ≥ ε + m , Compared with KRR (3.2), a common consensus is that l q -KRS (4.1) may bring a certain additional interest such as the sparsity for suitable choice of q. However, it should be noticed that this assertion may not always be true. This conclusion depends heavily on the value of the regularization parameter. If the the regularization parameter is extremely small, then l q -KRS for any q ∈ (0, ∞) behave similar as the least squares. Under this circumstance, Theorem 4.1 obviously holds due to the conclusion of Theorem 3.1. To distinguish the character of l q -KRS with different q, one should consider a relatively large regularization parameter. Theorem 4.1 shows that for a large range of regularization parameters, all the l q -KRS associated with the needlet kernel can attain the same, almost optimal, generalization error bound. It should be highlighted that the quantity m q−1 ε is, to the best of knowledge, almost the largest value of the regularization parameter among all the existing results. We encourage the readers to compare our result with the results in [15,28,29,32]. Furthermore, we find that m q−1 ε is sufficient to embody the feature of l q kernel regularization schemes. Taking the kernel lasso for example, the regularization parameter derived in Theorem 4.1 asymptotically equals to ε. It is to see that, to yield a prediction accuracy ε, we have According to the structural risk minimization principle and λ = ε, we obtain This implies naturally the sparsity of the kernel lasso estimate. Intuitively, the generalization capability of l q -KRS (4.1) with a large regularization parameter may depend on the choice of q. While from Theorem 4.1 it follows that the learning schemes defined by (4.1) can indeed achieve the same asymptotically optimal rates for all q ∈ (0, ∞). In other words, on the premise of embodying the feature of l q -KRS with different q, the choice of q has no influence on the generalization capability in the sense of rate optimality. Thus, we can determine q by taking other non-generalization considerations such as the smoothness, sparsity, and computational complexity into account. Finally, we explain the reason for this phenomenon by taking needlet kernel's perfect localization property in the spacial domain into account. To approximate f ρ (x), due to the localization property of K n , we can construct an approximant in H z,K with a few K n (x i , x)'s whose centers x i are near to x. As f ρ is bounded by M , then the coefficient of these terms are also bounded. That is, we can construct, in H z,K , a good approximant, whose l q norm is bounded for arbitrary 0 < q < ∞. Then, using the standard error decomposition technique in [7] that divide the generalization error into the approximation error and sample error, the approximation error of l q -KRS is independent of q. For the sample error, we can tune λ that may depend on q to offset the effect of q. Then, a generalization error estimate independent of q is natural.

Proofs.
In this section, we present the proof of Theorem 3.1 and Theorem 4.1, respectively.

Proof of Theorem 3.1.
For the sake of brevity, we set f n = K n * f ρ . Let Then it is easy to deduce that Therefore, we can rewrite the sample error as The aim of this subsection is to bound D n (λ), S 1 and S 2 , respectively. To bound D n (λ), we need the following two lemmas. The first one is the Jackson-type inequality that can be deduced from [20,24] and the second one describes the RKHS norm of f n .
Lemma 5.1. Let f ∈ W r . Then there exists a constant depending only on d and r such that where · denotes the uniform norm on the sphere.
Lemma 5.2. Let f n be defined as above. Then we have Proof. Due to the addition formula (2.1), we have Since it follows from the Funk-Hecke formula (2.2) that Therefore, This implies The proof of Lemma 5.2 is completed. Based on the above two lemmas, it is easy to deduce an upper bound of D n (λ). Proposition 5.3. Let f ∈ W r . There exists a positive constant C depending only on r and d such that In the rest of this subsection, we will bound S 1 and S 2 respectively. The approach used here is somewhat standard in learning theory. S 2 is a typical quantity that can be estimated by probability inequalities. We shall bound it by the following one-side Bernstein inequality [7]. Lemma 5.4. Let ξ be a random variable on a probability space Z with mean E(ξ), variance σ 2 (ξ) = σ 2 . If |ξ(z) − E(ξ)| ≤ M ξ for almost all z ∈ Z. then, for all ε > 0, By the help of the above lemma, we can deduce the following bound of S 2 . Proposition 5.5. For every 0 < δ < 1, with confidence at least Proof. It follows from Lemma 2.2 that f n ∞ ≤ M , which together with |f ρ (x)| ≤ M yields that which implies that Now we apply Lemma 5.4 to ξ 2 . It asserts that for any t > 0, This implies the desired estimate. It is more difficult to estimate S 1 because ξ 1 involves the sample z through f z,λ . We will use the idea of empirical risk minimization to bound this term by means of covering number [7]. The main tools are the following three lemmas.
where c is a positive constant and N (π M V k , η) is the covering number associated with the uniform norm that denotes the number of elements in least η-net of π M V k . Lemma 5.6 is a direct result through combining [16,Property 1] and [17, P.437]. It shows that the covering number of a bounded functional space can be also bounded properly. The following ratio probability inequality is a standard result in learning theory [7]. It deals with variances for a function class, since the Bernstein inequality takes care of the variance well only for a single random variable.
Lemma 5.7. Let G be a set of functions on Z such that, for some c ≥ 0, |g − E(g)| ≤ B almost everywhere and E(g 2 ) ≤ cE(g) for each g ∈ G. Then, for every ε > 0, Now we are in a position to give an upper bound of S 2 . Proposition 5.8. For all ε > 0, Proof. Set Therefore, Since |π M f | ≤ M and |f ρ (X)| ≤ M almost everywhere, we find that almost everywhere. It follows that |g(z) − E(g)| ≤ 16M 2 almost everywhere and Now we apply Lemma 5.7 with B = c = 16M 2 to the set of functions F and obtain that Observe that for g 1 , g 2 ∈ F there exist f 1 , f 2 ∈ π M H K such that In addition, for any f ∈ π M H K , there holds We see that for any ε > 0, an ε 4M -covering of π M H K provides an ε-covering of F . Therefore Then the confidence is it follows from (5.3) and Lemma 5.6 that This finishes the proof. Now we are in a position to deduce the final learning rate of the kernel ridge regression (3.2). Firstly, it follows from Propositions 5.3, 5.5 and 5.8 that holds with confidence at least Then, by setting ε ≥ ε + ≥ C(m/ log m) −2r/(2r+d) , n = c 0 ε −1/(2r) and λ ≤ M −2 ε, we get, with confidence at least there holds The lower bound can be more easily deduced. Actually, it can be easily deduced from the Chapter 3 of [9] that for any estimator f z ∈ Φ m , there holds where ε 0 = 1 2 and ε − = cm −2r/(2r+d) for some universal constant c. With this, the proof of Theorem 3.1 is completed.

Proof of Theorem 4.1.
Before we proceed the proof, we at first present a simple description of the methodology. The methodology we adopted in the proof of Theorem 4.1 seems of novelty. Traditionally, the generalization error of learning schemes in the sample dependent hypothesis space (SDHS) is divided into the approximation, hypothesis and sample errors (three terms) [32]. All of the aforementioned results about coefficient regularization in SDHS fall into this style. According to [32], the hypothesis error has been regarded as the reflection of nature of data dependence of SDHS, and an indispensable part attributed to an essential characteristic of learning algorithms in SDHS, compared with the learning schemes in SIHS (sample independent hypothesis space). With the needlet kernel K n , we will divide the generalization error of l q kernel regularization into the approximation and sample errors (two terms) only. The core tool is needlet kernel's excellent localization properties in both the spacial and frequency domain, with which the reproducing property, compressible property and the best approximation property can be guarantee. After presenting a probabilistic cubature formula for spherical polynomials, we can prove that all the polynomials can be represented by via the SDHS. This helps us to deduce the approximation error. Since H z,K ⊆ H K , the bound of the sample error is as same as that in the previous subsection. Thus, We divide the proof into three parts. The first one devotes to establish the probabilistic cubature formula. The second one is to construct the random approximant and study the approximation error. The third one is to deduce the sample error and derive the final learning rate.
To present the probabilistic cubature formula, we need the following two lemmas. The first one is the Nikolskii inequality for spherical polynomials [24].
Lemma 5.9. Let 1 ≤ p < q ≤ ∞, n ≥ 1 be an integer. Then where the constant C depends only on d.
To state the next lemma, we need introduce the following definitions. Let V be a finite dimensional vector space with norm · V , and U ⊂ V * be a finite set. Here V * denotes the dual space of V. We say that U is a norm generating set for V if the mapping T U : V → R Card(U ) defined by T U (x) = (u(x)) u∈U is injective, where Card(U) is the cardinality of the set U and T U is named as the sampling operator. Let W := T U (V) be the range of T U , then the injectivity of T U implies that T −1 U : W → V exists. Let R Card(U ) have a norm · R Card(U) , with · R Card(U) * being its dual norm on R Card(U ) * . Equipping W with the induced norm, and let T −1 U := T −1 U W→V . In addition, let K + be the positive cone of R Card(U ) : that is, all (r u ) ∈ R Card(U ) for which r u ≥ 0. Then the following Lemma 5.10 can be found in [19].
holds with confidence at least Proof. Without loss of generality, we assume Q n ∈ P 0 := {f ∈ Π d n : f p ≤ 1}. We denote the δ-net of all f ∈ P 0 , by A(δ). It follows from [13,Chap.9] and the definition of the covering number that the smallest cardinality of A(δ) is bounded by exp{Cn d log 1/δ}. Given Q n ∈ P 0 . Let P j be the polynomial in A(2 −j ) which is closet to Q n in the uniform norm, with some convention for breaking ties. Since Q n − P j → 0, with the denotation η i (P ) = |P (t i )| p − P p p , we can write Since the sampling set Λ N consists of a sequence of i.i.d. random variables on S d , the sampling points are a sequence of functions t j = t j (ω) on some probability space (Ω, P). If we set ξ p j (P ) = |P (t j )| p , then where we have used the equalities Furthermore, It follows from Lemma 5.9 that Hence Moreover, using Lemma 5.9 again, there holds, Then, using Lemma 5.4 with ε = 1/2 and M ξ = σ 2 = Cn d , we have for fixed P ∈ A(1), with probability at most 2 exp{−CN/n d }, there holds Noting there are at exp{Cn d } polynomials in A(1), we get Now, we aim to bound the probability of the event: (e1) for some l ≥ 1, some P ∈ A(2 −l ) and some Q ∈ A(2 −l+1 ) with p − q ≤ 3 × 2 −l , there holds The main tool is also the Bernstein inequality. To this end, we should bound |η i (P ) − η i (Q) − E(η i (P ) − η i (Q)) and the variance σ 2 (η i (P ) − η i (Q)). According to the Taylor formula and Lemma 5.9, we have If P ∈ A(2 −l ) and Q ∈ A(2 −l+1 ) with P − Q ≤ 3 × 2 −l , then it follows from Lemma 5.4 again that, Since there are at most 2 exp{−Cn d log l} polynomials in A(2 −l ) ∪ A(2 −l+1 ), then the event (e1) holds with probability at most Since ∞ i=1 e −a l b ≤ Ce −b for any a > 1 and b ≥ 1, we then deduce that Thus, it follows from (5.4) and (5.5) that with confidence at least This means that with confidence at least Now, we use (5.6) and Lemma 5.10 to prove Lemma 5.11. In Lemma 5.10, we take V = Π d n , Q n V = Q n p , and W to be the set of point evaluation functionals The operator T W is then the restriction map Q n → Q n | Λ , with It follows from (5.6) that with confidence at least We now take u to be the functional By Hölder inequality, y V * ≤ |S d |. Therefore, Lemma 5.10 shows that holds with confidence at least This finishes the proof of Proposition 5.11. To estimate the upper bound of we first introduce an error decomposition strategy. It follows from the definition of f z,λ,q that, for arbitrary f ∈ H K,z , Since f ρ ∈ W r with r > d 2 , it follows from the Sobolev embedding theorem and Jackson inequality [4] that there exists a P ρ ∈ Π d n such that Then we have where D(z, λ, q) and S(z, λ, q) are called as the approximation error and sample error, respectively. The following Proposition 5.12 presents an upper bound for the approximation error.
Proposition 5.12. Let m, n ∈ N, r > d/2 and f ρ ∈ W r . Then, with confidence at least 1 − 2 exp{−cm/n d }, there holds where C and c are constants depending only on d and r.
Proof. From Lemma 2.2, it is easy to deduce that Thus, Proposition 5.11, Hölder inequality and r > d/2 yield that with confidence at least 1 − 2 exp{−cm/n d }, there exists a set of real numbers {a i } m i=1 satisfying m i=1 |a i | q ≤ 2|S d |m 1−q for q > 0 such that The above observation together with (5.7) implies that with confidence at least 1 − 2 exp{−cm/n d }, P ρ can be represented as such that for arbitrary f ρ ∈ W r , there holds and where C is a constant depending only on d and M . It thus implies that the inequalities (5.8) D(z, λ, q) ≤ P ρ − f ρ 2 ρ + λΩ q z (g * ) ≤ C n −2r + 2λ|S d |m 1−q holds with confidence at least 1 − 2 exp{−cm/n d }.
6. Conclusion and discussion. Since its inception in [24], needlets have become the most popular tools to tackle spherical data due to its perfect localization performance in both the frequency and spacial domains. The main novelty of the present paper is to suggest the usage of the needlet kernel in kernel methods to deal with spherical data. Our contributions can be summarized as follows. Firstly, the model selection problem of the kernel ridge regression boils down to choosing a suitable kernel and the corresponding regularization parameter. Namely, there are totally two types parameters in the kernel methods. This requires relatively large amount of computations when faced with large-scaled data sets. Due to needlet kernel's excellent localization property in the frequency domain, we prove that, if a truncation operator is added to the final estimate, then as far as the model selection is concerned, the regularization parameter is not necessary in the sense of rate optimality. This means that there is only a discrete parameter, the frequency of the needlet kernel, needs tuning in the learning process, which presents a theoretically guidance to reduce the computation burden. Secondly, Compared with the kernel ridge regression, l q kernel regularization learning, including the kernel lasso estimate and kernel bridge estimate, may bring a certain additional attribution of the estimator, such as the sparsity. When utilized the l q kernel regularization learning, the focus is to judge whether it degrades the generalization capability of the kernel ridge regression. Due to needlet kernel's excellent localization property in the spacial domain, we have proved in this paper that, on the premise of embodying the feature of the l q (0 < q < ∞) kernel regularization learning, the selection of q doesn't affect the generalization error in the sense of rate optimality. Both of them showed that the needlet kernel is an good choice of the kernel method to deal with spherical data.