Information Dynamics in Complex Systems Negates a Dichotomy between Chance and Necessity

: Entropy increases in the execution of linear physical processes. At equilibrium, all uncertainty about the future is removed and information about the past is lost. Complex systems, on the other hand, can lead to the emergence of order, sustain uncertainty about the future, and generate new information to replace all old information about the system in finite time. The Kolmogorov–Sinai entropy for events and the Kolmogorov–Chaitin complexity for strings of numbers both approximate Shannon’s entropy (an indicator for the removal of uncertainty), indicating that information production is equivalent to the degree of complexity of an event. Thus, in the execution of non-linear processes, information entropy is inseparably tied to thermodynamic entropy. Therein, the critical decision points (bifurcations), which can exert lasting impact on the evolution of the future (the “butterfly effect”), defy the definition of being either born from randomness or from determination. Nevertheless, their information evolution and degree of complexity are amenable to measurement and can meaningfully replace the dichotomy of chance versus necessity. Common anthropomorphic perceptions do not accurately account for the transient durability of information, the potential for major consequences by small actions, or the absence of a discernible opposition between coincidence and inevitability.

The terms "chance" and "necessity" are part of the daily vocabulary. However, they have been difficult to define rigorously [1]. Simply the delineation of what is lawful and what is random has been subject to debate. Karl R. Popper wrote about the differentiation of planetary movements as lawful and of throws of dice as chance events that, thus far, prognoses of planetary orbits have been successful while prognoses of individual throws of dice have not. Extending a rationale developed earlier by Kurt Gödel, Popper demonstrated that self-prediction from within a system is impossible, and he was consecutively led to become an indeterminist [2].
The concept of randomness may be characterized in various ways as an event without a perceivable design (Appendix 1). The lack thereof can be reflected in the "random" mechanism of generation or in the "random" pattern of output.
-Uncertainty in the mechanism that generates specific outcomes may produce randomness. The throwing of dice is such a mechanism of uncertainty. Likewise, a string of numbers is random if it is generated by an unpredictable mechanism [3]. The randomness resides in the disorder of the generating process. - The arrangement of a pattern or a string of numbers may reflect randomness. A string is random because there is no inherent design that allows the prediction of consecutive digits or because there are no simple rules that enable the description of the string in compressed form [4]. The randomness lies in the arrangement itself.
Information (the removal of uncertainty, Appendix 2) and complexity (non-linearity, not amenable to closed-form solutions) are intricately linked to our everyday understanding of chance, but unlike "chance" or "randomness" these physical entities can be subjected to rigorous definition and analysis. Whereas no information is yielded by equilibrium (stasis), information flow (more accurately information evolution [5]) is tied to an occurrence (Section 1). The complexity of that occurrence underlies the amount of new information generated (Sections 2,3), and it produces emergent phenomena (Section 4). At the bifurcations that are inherent in non-linear systems, infinitesimal influences can yield dramatically divergent results (Section 4), but any analysis of deterministic versus indeterministic foundations for complex processes is bound to be unsuccessful (Sections 5,6). Substantial implications derive from the transience of information, the potential for major consequences by small actions at decision points (bifurcations), and the breakdown of the dichotomy between chance and necessity.

Information is the Removal of Uncertainty
The information content of an event is principally quantifiable in the algorithms developed by Claude Shannon [6]. An event with a certain outcome (a probability of 1) yields no new information. The information content of a process is interpretable as the removal of the extent of uncertainty that exists before its execution. This uncertainty constitutes the random or chance component inherent in this process. With its execution, the random element is removed, and new information is communicated.
In Shannon's model, communication takes place between a sender and a receiver via a channel, the capacity of which is a critical determinant that is calculated from its noise characteristics. For all communication rates below channel capacity, the probability of error can in principle become arbitrarily small. However, theoretically optimized communication schemes may be computationally impractical. Random processes have an irreducible complexity, below which the signal cannot be compressed. The ultimate data compression is dubbed the entropy (Appendix 3 and Appendix 4). Entropy and mutual information are functions of the probability distributions that underlie the process of communication.

Information Has a Finite Lifespan
A swinging pendulum must eventually come to a halt. Once at rest, the history of its swing cannot be reconstructed by any means. The second law of thermodynamics states that a closed system progresses toward a state of maximal entropy. Once this state is reached, all information on the path that led to it is lost, as is any uncertainty about its future. Thermodynamics (Appendix 5) has introduced the asymmetry of time irreversibility into physical law, and it has established the inescapability of losing information about the past (a form of "collective forgetting").
The energy of physical systems is describable on the macroscale, which in classical mechanics is completely intelligible and can be captured with deterministic algorithms, versus the micro-scale of thermal motion, which is randomly distributed and can be expressed only as averages over large numbers. In the epochs preceding non-linear systems research, the states of the microscales were assumed to be uniform or stochastic and to constitute a lower limit of feasible explanation [7]. An adjustment of this concept is required in non-linear events that arise far from equilibrium, where energy is believed to emerge from the microscales and affect the macroscopic outcome [8].
In dynamics, motion can be depicted as a flow along trajectories in a phase space that often maps momentum versus position variables (sometimes velocity versus position) [9,10]. This phase space has as many dimensions as the system has degrees of freedom. In laminar flow, motion is governed by boundary and initial conditions, and no new information is generated, as outlined above. In turbulent flow, information is continuously generated by the flow itself through an exchange between the micro-and macro-scales. The average rate of information production (bits of information per unit time, denoted as ̅ ; the term is identical to the Lyapunov characteristic exponent [11]) is a measure for the rate of divergence of nearby trajectories (Appendix 6). The transition of a system from laminar to turbulent behavior is reflected in a change of the Lyapunov characteristic exponent from negative to positive, corresponding to a change of the system from an information sink to an information source, even if this turbulent behavior is governed by simple system equations. The Lyapunov characteristic exponent is a system state function that remains invariant under coordinate transformations. The information generated anew by turbulent systems precludes prediction past a certain time, when new information has accumulated to entirely displace the initial data. "New information is continuously being injected into the macroscopic degrees of freedom of the world by every puff of wind and every swirl of water" [8]. The loss of information about the initial state of a system is a physical reality, whether the occurring process strives toward equilibrium or toward emergence.

Information and Complexity are Equivalent
An occurrence in phase space, state space, or event space is characterized by its occupancy of the attributed space. In essence, such an analysis of occurrences in abstract space removes the definition of dimensions from to the axes of concrete space and relieves its restriction to whole numbers. The application of the Lyapunov characteristic exponent ̅ to such a conceptual space yields a measure for the information flow (or the information evolution) associated with each step in the execution of the event (Appendix 7). It lays the foundation for the calculation of a fractal dimensionality, the Lyapunov dimension, that characterizes the information evolution of the event in its entirety. This dimensionality gives an estimate of the Kolmogorov-Sinai entropy [12], which defines the information change inherent in the execution of the process. The Lyapunov dimension DKY represents an upper bound for the information dimension of the system (Appendix 8).
= + λ λ k = maximum integer such that the sum of the k largest exponents is non-negative; ̅ = Lyapunov characteristic exponent. The insertion of the Lyapunov characteristic exponent into this formula achieves the connection between the complexity of a process, the execution of which impacts thermodynamic entropy development, to its information entropy.
As non-linear systems dynamics studies algorithms that do not have closed-form solutions (Appendix 9), its analyses draw heavily on information theory [13]. Complexity has been measured in simple strings of 0s and 1s. A string is random if its shortest description is obtained by writing it out in its entirety-the shortest description of the string is the string itself. The more compressible the string, the less random it is. Connecting complexity and information content, the Kolmogorov-Chaitin complexity (K) of a string is approximately equal to the Shannon entropy (H), if the sequence of the string under study is drawn at random from a distribution that has the entropy H [14]. Specifically, for almost all infinite sequences produced by a stationary process, the growth rate of the Kolmogorov-Chaitin complexity is equal to the Shannon entropy rate. More broadly, diverse measures for information change, entropy and dimensionality in conceptual space are interdependent ( Table 1), suggesting that these modalities of assessment largely equate to each other.

Complexity Drives Emergence via Critical Decision Points
Complex systems are characterized by non-periodic flow with sensitive dependence on the starting conditions, emergence of properties from non-equilibrium states, and generation of new information to fully replace old information. Hence, there are limits to how precisely we can describe the evolution of non-linear processes. Uncertainty about the future grows rapidly. Further, in the progression of complex systems there exist decision points, at which infinitesimal influences can propel events onto one of several very different future paths. Proceeding in this manner, the emergence of ordered structures from non-equilibrium conditions has been described in physics [15], chemistry [16,17] and evolution [18].
States in thermodynamic equilibrium (or states that equate to a minimal entropy production in the linear thermodynamics of non-equilibrium) are stable states that are principally reversible. Yet, irreversible processes play a fundamental and constructive role in the physical world. The laws of irreversible processes [10] have embedded dynamics in a more comprehensive formalism that includes unstable states. Non-equilibrium can lead to dissipative structures, wherein fluctuations introduce a stochastic description into the macroscopic level. Instabilities far from equilibrium are essential elements for emerging systems [19].
Evolution has been investigated as occurring in a conceptual state space, the shape of which is defined by the distribution of properties across an ensemble (a fitness landscape; Appendix 10). The initiating event for every step in evolution is a change (a mutation). Once a mutation has taken place, its penetration of the population is subjected to the rule of selection. However, simple and complex systems can exhibit powerful self-organization, and the effects of mutation and selection are diminished when operating on systems that have their own robust self-ordered properties. Spontaneous order is maintained despite selection, not because of it. Selection may only be able to mitigate the tendency for adaptive processes to become trapped on continuously lower local optima of fitness as complexity increases. While the selective force is stronger than the mutational force below a critical complexity of an organism, above this critical complexity, the dispersing mutational pressure increases, and the population falls from the global optimum to a suboptimal stationary steady state. Hence, the outcome of selection is context dependent. It drives or maintains complex systems on the boundary between order and chaos (sometimes dubbed "the edge of chaos" or "the onset of chaos"). At that boundary ("the poised state"), systems are best able to coordinate complex tasks and evolve in a complex environment [18].
A lack of periodicity is very common in nature. It is one of the distinguishing features of complex systems, for which progression and advanced states are unpredictable [20]. Events that are governed by non-linear differential equations have traditionally been considered deterministic on the basis of their driving algorithms, even though the slightest immeasurable deviations in their initial states can lead to dramatically different outcomes. For a finite system of ordinary differential equations representing forced dissipative flow, frequently, all of its solutions are ultimately confined within the same bounds. For these equations, non-periodic solutions cannot readily be determined, except by numerical procedures. The evolution of dissipative systems under these equations is commonly modeled with trajectories in phase space. Prediction of the sufficiently distant future is not feasible by any method, unless the initial conditions are known exactly (an impossible feat, as detailed in Section 5 below). There is an eventual necessity for any bounded system of finite dimensionality to come arbitrarily close to acquiring a state it has previously assumed. Only if the system is stable will its future development then remain arbitrarily close to its past history, and it will be quasi-periodic. Unstable systems display the now-famous "butterfly effect": one flap of a butterfly's wings may change the future course of the weather in a place far away. "The result […] implies that two states differing by imperceptible amounts may eventually evolve into two considerably different states. If, then, there is any error whatever in observing the present state -and in any real system such errors seem inevitable-an acceptable prediction of an instantaneous state in the distant future may well be impossible." [21].

At the Critical Decision Points, Randomness Versus Determination is Undecidable
It is principally impossible to assess whether decision points, such as bifurcations, are governed by deterministic or indeterministic mechanisms. Phase space models have minimally discernible resolution (Appendix 11), description beyond which is infeasible [8]. Thermodynamic considerations striving to incorporate irreversibility into physical law have developed event space models, wherein internal time and entropy become operators. The resolution of the description is restrained by the eigenvectors and eigenvalues of the operators [10].
Non-linear systems research often describes events as trajectories in phase space. Such phase space is divisible into blocks of minimum size that represent states. Their expansions constitute the limits to the precision of obtainable knowledge. Progressive attempts to more precisely measure the system eventually lead to the microscopic scale, wherein the uncertainty principle assures that the more accurately the position in phase space is determined, the less accurately the velocity can be assessed [22]. The analogous relationship exists between energy and time. Two trajectories become indistinguishable after they have approached each other below the distance of a block size. At the heart of non-linear systems are bifurcation points, where a system can evolve either toward one state or toward another, yielding very different outcomes. The infinite accuracy of measurement at the bifurcation point that would be required to predict which state a system will assume is impossible. Hence, the unpredictability of complex systems is rooted in the physical limit on the precision of obtainable knowledge [23].
In the vicinity of decision points (bifurcations), predictability under the law of large numbers is not valid anymore. While the molecular interactions in chemical reactions or mechanical motion far from equilibrium do not change from those in equilibrium, they do become dependent on global conditions. The transition from the time-reversible formulas of chemistry or mechanics to the algorithms of emerging processes is accomplished through a unique form of a non-local transformation, in which the homogeneity of the space-time structure is eliminated and both entropy and time become operators in an event space. This transition involves an internal time that is derived from the uncertainty associated with the trajectories in unstable dynamic systems. The transformation leads to a spatiotemporally non-local description [19]. Intelligibility is limited to the eigenvectors and eigenvalues of the operators.

Complexity and Chance are Mirror-Images of the Same Events
Any discrete process, which maps the interval onto itself and whose reverse process is doubleor multiple-valued, fulfills the Li and Yorke criterion for chaos. Sequences of numbers obtained by iteration of such processes (t indicates iteration steps) are mirror images of paths of random walks in the reverse, branched processes [24]. A deterministic system may be defined as one whose future and past are both unique functions of the present. On this basis, the difference equation (the logistic map equation) is which is not deterministic because there are two different pasts of equal probability, even though the future is a unique function of the present. Iteration of the latter equation is still possible if rules are defined to choose one of the two values. Generally, for any one-dimensional map, what is unstable in the iteration of the forward process is stable in the iteration of the inverse process and vice versa. If iteration of the inverse equation is performed with random choices at each step, there will be no convergence toward a point or a cycle. The mirror image of this iteration will be a chaotic sequence produced by the initial difference equation, as is evidenced if the last number of a sequence produced by the inverse equation with random decision making at each iteration is used as the first number of an iteration of the initial difference equation, which will yield the same sequence in reverse. That is, the same sequence of numbers can be produced by a stochastic as well as by a deterministic process. Chaos in a one-dimensional difference equation can be viewed as reversed random walk [25].

Conclusions
The present analysis shows that the perception of a dichotomy between determined and undetermined elements of the world is an artifact, generated by the human mind. A distinction between a "random" occurrence and a complex "deterministic" occurrence is impossible to make as it has no correlate in nature. Models in phase space (typically plotting impulse versus time) or event space (an operator space) inherently have insufficient resolution to enable an assessment in favor of one or the other (Section 5). Strings of numbers can reflect deterministic chaos (a form of complexity) or randomness, depending on the order in which they are encountered (Section 6). By contrast, we are enabled to measure new information produced by an event (through the Lyapunov characteristic exponent) and the degree of complexity inherent in the event (through the information dimension) in order to gain relevant, quantitative readouts (Section 3). Rather than a dichotomy between chance and necessity, quantifiable information evolution and information dimension, as well as entropy, are suitable scientific measures for the complexity of an occurrence, which can be interpreted as being reflective of the "ordered" and "chance" components that contribute to this occurrence [5].
The universe is one coherent entity. Nevertheless, the traditional, reductionist description of nature has typically categorized observations and created opposites that are purportedly mutually independent, thus generating partial entities of the world that have been treated as detached from one another. Such categorizations had the benefit of achieving tractability through a quasilinearization of descriptions [26]. The construct of a dichotomy between necessary events and chance events enabled us-especially in the eras preceding computers and complexity research-to make meaningful observations about parts of the world. However, it has given rise to centuries of discussions about world views that span the entire spectrum from deterministic fatalism to indeterministic nihilism. The results from non-linear systems research must lead to the conclusion that the dichotomous perception itself is untenable. There is no meaningful answer to the question whether a complex event has originated in chance or necessity. Only readouts for its extent of complexity are meaningful assessments.
Human societal value systems are often rooted in the idea of name recognition as a modality of acknowledgement for achievement. For fame we compete. Yet, the present analysis has shown that information generally has a finite lifespan. Eventually, name recognition-like all information-will be replaced and the name will turn into smoke. Societies are emergent systems wherein new information will eventually entirely replace old information. By contrast, miniscule actions at decision points (bifurcations) of complex systems can have an irreversible and durable impact on the future. In keeping with natural laws, actions-even small representations thereof-may deserve priority over attribution of credit as the measure for contributions to progress.
Funding: This research received no external funding.

Conflicts of Interest:
The author declares no conflict of interest.

Appendix A
1. For a discussion of chance versus randomness see Eagle [27]. As the present discussion negates the physical possibility to resolve the dichotomy between chance and necessity, the more subtle distinction between chance and randomness becomes moot. Information flow (or information evolution) and complexity (fractal dimensionality) are amenable to measurements and offer well suited replacements for the difficult-to-define terms "chance", "randomness", "necessity" and "determination" in the description of nature.
2. Randomness is often explicated as unpredictability [28]. Hence, uncertainty is a reflection of the random components of an event.
3. The formal convergence between the Shannon formula for entropy in information theory and the Boltzmann formula for thermodynamic entropy has given rise to extensive debates over meaningful connections between them. They have a common origin in probability theory, and they need to satisfy common requirements such as additivity. "If one accepts the probabilistic interpretation of the entropy, and agrees on the meaning of Shannon's information, then the interpretation of the thermodynamic entropy as thermodynamic information becomes inevitable" [29].
Other formulations of entropy have been proposed, which measure complexity in dynamical systems (Kolmogorov-Sinai entropy; see Section 3) or in strings of numbers (Kolmogorov-Chaitin complexity). They share with the Shannon entropy the dependence on information. While Kolmogorov-Chaitin complexity is concerned with the content of information, Shannon entropy is concerned with the missing information.
4. The Rényi entropy [30] is a generalization of the Shannon entropy. In the limit where the order approaches 1, the Rényi definition of entropy converges to the Shannon definition. An attractor for which the Rényi dimensions are not all equal exhibits multifractal structure. Thus, the Rényi dimension connects uncertainty to the dimensionality of the space (state space, phase space or event space), in which it is measured.
5. The concept of entropy was developed in the 1850s by Rudolf Clausius, who described it as the transformation content (dissipative use of energy) of a thermodynamic system or working body of chemical species during a change of state. Much of the mathematics for the field of thermodynamics was then formulated in the 1870s by Ludwig Boltzmann and J. Willard Gibbs.
6. Stable periodic orbits have a Lyapunov characteristic exponent ( ̅ ) that is negative. Only in the hypothetical case of ̅ = 0 can transients persist indefinitely and information on the underlying perturbation of the system be preserved.
7. To be consistent with the second law of thermodynamics, proper equations of motion must allow for the existence of an attractor. This is not the case for Newton's laws or for Lagrangian and Hamiltonian mechanics, but it is achievable through the redefinition of entropy and an internal time in the form of operators. This description of dynamics in terms of operators dramatically reshapes space-time [10,19]. However, due to the reliance on the eigenvectors and eigenvalues of the operators for time and thermodynamic entropy, an assessment of the information evolution associated with an event now requires algorithms that are independent of trajectories in phase space. To achieve this, a reformulation of the Lyapunov characteristic exponent has been applied to the vector-based event space [5].
8. Sinai and Kolmogorov built on the Shannon concept of information entropy to determine a measure for the complexity of the motion taking place in a dynamical system. Pesin later demonstrated that, when the Kolmogorov-Sinai entropy is greater than 0, the dynamical system will display non-linearity (chaos). According to Pesin's theorem [31], the sum of all the positive Lyapunov exponents gives an estimate of the Kolmogorov-Sinai entropy. 9. In non-periodic flow, closed-form predictions are impossible because the information they would represent simply does not exist prior to the operation of the mechanism. 10. The movement over a fitness landscape is an alternative model to the progression of a trajectory in phase space.
11. "As soon as any trajectories approach within some distance h of each other, they will become indistinguishable. In any physical implementation of the system h may vary depending on the accuracy of the instrument measuring the system position, the thermal motion of the system, or many other factors. However, even with "perfect" instruments and at absolute zero, h can never be reduced to zero. The Uncertainty Principle assures us that there is a minimum block size in phase space, which is a physical constant of Nature. Should two orbits arrive within such a block, they are no longer distinguishable, and the information represented in their separate origins is lost." [8]


Expert system for predicting the state of transformers based on fuzzy logic

The article examines methods for monitoring the operation of oil-filled transformers and identifies methods for evaluating the state of the transformer using a fuzzy logic device. Solutions for remote analysis of transformer operation have been formed. The methods that were used for diagnostics are presented. Conclusions are drawn on which equipment is more effective for diagnostics of power transformers.

Introduction
Currently, substations use physically and morally outdated equipment, which can lead to failures and loss of electricity for consumers. One of the most important basic elements of TP electrical equipment is a power transformer. Its repair in case of damage is associated with a large expenditure of labor and money. Emergency foci occur primarily due to long-term operating time and significant physical wear and tear.

Materials and methods
An expert system for predicting the state of transformers based on fuzzy logic should solve a number of tasks aimed at improving the accuracy of the diagnostic result. The sequence of actions of the system is presented as follows: • Processing of the survey results; • Comparison procedure with the results of previous diagnostics in different operating modes; • The calculation procedure of the fuzzy data in numerical format; • The final output.
One of the main advantages of an expert system based on fuzzy logic is the ability to represent the knowledge base using a linguistic language. Thus, the database can be supplemented, expanded, and edited by a human expert without appropriate programming training.
The introduction of additional characteristics, of course, will require special knowledge in this area, but working with existing characteristics is possible at a simpler level [1][2].
Based on the results of the system, a report is generated that describes each analyzed situation from the fuzzy knowledge base, shows the results of mathematical processing of diagnostic data, and IOP Conf. Series: Materials Science and Engineering 976 (2020) 012001 IOP Publishing doi:10.1088/1757-899X/976/1/012001 2 indicates the numerical values of the degree of confidence for each answer to the questions asked to the system.
Because the diagnostic features are random, the system uses modified functions based on the Gaussian membership function: where: u is the abscissa, b is the maximum coordinate, and c is the concentration coefficient.
The degrees of significance of various parameters obtained in the table for evaluating the state of transformers already allow the expert to draw conclusions about the state of transformers, but it is possible to get a much more accurate expert assessment based on fuzzy logic methods. To develop such a system, we chose the SciLab software.
SciLab has a special Fuzzy Logic Toollbox add-on for working with fuzzy logic tools. For the features highlighted in the table, we will set the linguistic values of variables corresponding to the degree of overheating according to thermal imaging data, the moisture content in the oil, the flash point, and the pH factor of the oil. Additionally, to improve the accuracy of evaluating the state of transformers, we will re-evaluate these characteristics on a 10-point scale.
When assessing the condition of equipment by excess temperature, the following areas are distinguished by the degree of malfunction: Excessive temperature-(5...10) °C. With a mean initial degree of fault that should be kept under control and take steps to eliminate it during repairs, scheduled according to the schedule. Excessive temperature -(10...30) °C, indicates a developed defect. In this case, it is necessary to take measures to eliminate the fault when the electrical equipment is taken out of operation as soon as possible.
Excessive temperature -more than 30°C means an emergency defect. Requires an immediate solution.
Because of the analysis of table 1, the transformer membership functions were obtained and entered into SciLab. Similarly, we will identify the linguistic rules.

Results
For oil-filled transformers, these rules will be as follows: • Degree of overheating according to thermal monitoring data: initial degree, developed defect, emergency defect; • Oil moisture concentration -acceptable, risk area, unacceptable; • Flash point -acceptable and unacceptable; • pH factor of the oil -acceptable and unacceptable.   In the first case, we selected only the first two characteristics from the table in Appendix A, so it is possible to visualize the input state using the built-in SciLab graphical tools. Figure 4 shows a surface that reflects the state of the fuzzifier output depending on the input values.  For the other two characteristics that reflect the features detected during transformer diagnostics, membership functions were also compiled. Their views are presented in figures 19-20. Figure 5-6 on the y-axis shows the weight of input status of fuzzifier. Comparing them with the previous ones, you can notice the appearance of the third state.

Discussion
After entering all the necessary data and setting the rules that connect the inputs and outputs, it is possible to perform aggregation and defuzzification to obtain an accurate value for the probability of replacing the transformer.
Aggregation is a procedure for determining the degree of truth of conditions for each of the rules of the fuzzy inference system. In this case, the values of the membership functions of the terms of linguistic variables that make up the above-mentioned conditions (antecedents) of the cores of fuzzy production rules obtained at the fuzzification stage are used [7][8].
Currently, the following algorithms are most used in fuzzy inference systems. The Mamdani algorithm found application in the first fuzzy automatic control systems. It was proposed in 1975 by the English mathematician E. Mamdani to control a steam engine.
Defuzzification is performed using the center of gravity or center of area method. Defuzzification using the center of gravity method is described by the following formula: In our case, this method was used. Figure 8 shows a view of the function of aggregated output values and a clear value of the probability of replacing the transformer in the case when the expert entered 2 and 4 ratings for mechanical damage and discharge density, respectively, in the system. Further, the expert evaluation method consists in applying the received values of the probability of transformer failure to the input of a new fuzzifier and obtaining one value for the state of the transformers based on four input data. The fuzzifier inputs are configured as Gaussian functions. In this case, the information is no longer entered as an estimate on a scale from 1 to 10, but as a percentage of the probability of finding the transformer in a particular state. The outputs of the final solution fuzzifier also have Gaussian membership functions, and the set of final solutions can be represented as a 3D graph [9][10].

Conclusion
The technical condition of the power transformer is characterized by a large number of parameters. With a large number of different data, the assessment of the technical condition of the power transformer is much more complicated. To solve this problem, you can use a fuzzy logic device. In this paper, based on a mathematical model, a method is developed for evaluating the technical condition of power transformers. This mathematical model is based on fuzzy logic, which can be trained using genetic algorithms. Using the device based on a fuzzy model of the technical condition of the power transformer will improve the quality of the assessment of the technical condition of the equipment by excluding a person when analyzing data. In addition, this will allow us to develop a number of similar programs for complex diagnostics, covering the entire range of electrical equipment of transformer substations, as well as to develop a program for predicting the remaining life, based on the assessment of a comprehensive analysis of the technical condition of electrical equipment of transformer substations.


Adaptive Transformers for Learning Multimodal Representations

The usage of transformers has grown from learning about language semantics to forming meaningful visiolinguistic representations. These architectures are often over-parametrized, requiring large amounts of computation. In this work, we extend adaptive approaches to learn more about model interpretability and computational efficiency. Specifically, we study attention spans, sparse, and structured dropout methods to help understand how their attention mechanism extends for vision and language tasks. We further show that these approaches can help us learn more about how the network perceives the complexity of input sequences, sparsity preferences for different modalities, and other related phenomena.

Introduction
Learning richer representations from visual and text data is a central task to solve multi-modal learning. Attention-based methods have proven to be very useful in learning long term dependencies and forming richer representations of the input sequences. Numerous approaches Su et al., 2019;Li et al., 2019;Chen et al., 2019) have been proposed for learning visiolinguistic representations with transformers. Although these approaches have provided us with significant improvement on various benchmarks (language and visiolinguistic), the architectures used are overparameterized require extensive training lasting for several weeks using multiple objectives to form a generalized representation of the task to be addressed, which is then followed by fine-tuning on a downstream task. This workflow has become a concerning problem. It results in deep learning methodologies being inaccessible and increased carbon footprints (Strubell et al., 2019). In this work, we specifically explore adaptive methods.
We refer to Adaptive mechanisms as those methods that change their behavior during training/run time and adapt stochastically to the environment based on data heuristics (parameters) learned by encountering samples from the same data distribution optimized by an objective function. Alternative approaches such as pruning, distillation (Hinton et al., 2015) and quantization are rigid to some extent and induce some form of permanent modifications to the model. Adaptive methods enforce the network to learn parameters such that their behavior changes as per the complexity of the input sequence as perceived by the neural network. The code to reproduce the results in this work is publicly available at this link 1 .
Current self-attention approaches assume that the attention span of a head is invariant to the complexity of an input sequence. Attention heads can learn their optimal context size (Sukhbaatar et al., 2019), which results in a reduction of FLOPS. When an optimal attention span is learned, the amount of attention given to a particular input sequence by an attention head is determined by its context size. We show that the context size varies with the emergent complexity of the sequence, and spans can help us understand how much sensitive a layer is to an input sequence.
Training models with a quarter of a million parameters are not feasible and practical for most users. One effective way to facilitate neural network scaling is by making the weights of the network sparse. This configuration allows us to perform faster training of deeper networks with relatively less compute. To make attention distributions sparse, we use α entmax (Correia et al., 2019) to obtain probability distribution of weights. Normalized exponential functions like softmax cannot assign a zero attention weight. This property en-forces the context vector to stay dense, resulting in non-relevant sequences to be considered even though the network has discarded them by putting a deficient weight. Adaptive sparsity can make an attention head to learn richer distributions by oscillating the behavior of distribution to stay between softmax and sparsemax. We show that this behavior can help us understand preferences for the density of attention weight distribution and how it varies amongst each head about different modality.
We also study a form of regularization method called Layerdrop (Fan et al., 2019) to understand its regularization impact for multi-modal features. If the network can learn to drop identical layers (Data Driven pruning), then it can be regarded as an adaptive depth mechanism. We specifically use the Every other pruning method where the user specifies the drop rate because it offers maximal gains as suggested compared to its counterpart pruning methods. This method has proven to be effective in reducing the number of parameters and pruning layers during inference.
The contribution of this work is as follows: • The adaptive approaches have only been tested with linguistic features only. We extend these approaches to study how do they align to capture complex relationships between different modalities. We also study the effects of aligning these approaches to understand their compatibility through ablation analysis.
• We perform interpretability analysis to learn how these approaches can enhance our understanding of attention behavior and adaptive approaches.
• We provide experimental results on the recent adaptive approaches for the multi-modal input sequences.

LXMERT
We use LXMERT (Tan and Bansal, 2019) as the baseline architecture. The adaptive approaches can be combined with any other self-attention mechanism based transformer. LXMERT uses self and cross attention layers to jointly attend to image and text inputs (input sequence). Specifically, it takes a word-level sentence and object-level image embeddings. The encoder consists of three main components: language (9 layers) and visual (5 layers) encoder (single-modality) to form textual and image representations and cross-modality encoder (5 layers) to jointly attend to both these representations. Cross attention is responsible for forming the mapping between ROI features and textual representations. Since the architecture used is identical, we refer the readers to (Tan and Bansal, 2019) for a detailed description of pre-training strategies. The network used has been pre-trained on four objectives: Masked Cross Modality LM, Masked Object Prediction, Cross Modality Matching, and Image Question Answering. Faster RCNN is used to extract ROI features from the input images.

Adaptive Attention Span
Unlike dynamic attention, which assumes that all attention heads require the same amount of span, learning an optimal attention span enables the gathering of information as per the context size determined by the attention head. A max upper bound span limit is enforced on each head, which helps reduce computation and memory requirements. As proposed in (Sukhbaatar et al., 2019), different heads emphasize on different context depending upon the task it is addressing. We explicitly show that these spans vary significantly based on the complexity of the task. We use the same masking function with minor modification: (1) Here, z acts as a model's parameter. We initialize it with kaiming normal (He et al., 2015) distribution. m z is coupled with the attention weights. Hyperparameter R helps in controlling the softness of this attention distribution.
The attention head compute the similarities between current token t and past token r in the span [t − S, t) as: where K, Q and P t−r denote key, query vectors, and position embedding respectively. In the standard setting, attention weight distribution is obtained by applying softmax on the similarity vector.
The attention weights from Equation 3 are then processed by the masking function as: The masking function is a non-increasing function that applies a transformation to the input values of attention scores to keep them in range of [0, 1]. The parameters of m z are updated with model parameters to learn the optimal span.

Adaptive Sparse Attention
In order to make attention weights sparse, we use α entmax as proposed in (Correia et al., 2019). Specifically, softmax is replaced with α entmax to compute attention weights given attention scores in Equation 3.
α plays a crucial role in determining the behavior of an attention head. If α > 1, the weight distribution would move away from softmax's dense representation towards sparse mappings as its curvature changes. For α = 2, we obtain complete sparse mappings. The value of alpha oscillates between 1 and 2. It is set as a network parameter, which is jointly optimized in the training process. Different values of α will govern the behavior of the attention head.

LayerDrop
Layerdrop (Fan et al., 2019) is a method to reduce the depth of the transformer in a controlled manner. This method drops the identical sub-layers in the transformer determined by a pruning strategy. We follow the Every Other strategy, which drops the layer as specified by a drop rate. It has been noted that this pruning strategy works well as compared to Search on Valid and Data Driven pruning strategies. Let N denote the total number of layers in the network. Setting p = 1 implies that we are dropping one layer out of all the layers assigned for a modality. The number of remaining layers becomes N − p. Although the network will consist of an equivalent amount of parameters as that of N layers, all the operations will be carried out equivalent to operations in N − p layers. This strategy allows us to prune layers during inference time.

Experimental Setup
Visual Question Answering To solve the VQA task, given an image and a question related to it, the network is supposed to predict the right answer from the given set of answer choices. We performed all the experimentation on the VQA 2.0 dataset (Antol et al., 2015). The dataset consists of three sets with a train set containing 83k images and 444k questions, a validation set containing 41k images and 214k questions, and a test set containing 81k images and 448k questions. In this case, the network is asked to predict an answer from 3129 answer choices for a particular question.
Implementation We use the pre-trained weights provided by (Tan and Bansal, 2019). We fine-tune LXMERT to form visiolinguistic representations based on image and text sequences with adaptive approaches mentioned above. This operation is followed by a classifier that receives the concatenated pooled features of image and text to predict the answer. Fine-tuning is performed on a single P100 GPU with 128 batch size. Optimization is performed with Lookahead (

Experimental Findings and Results
Adaptive span for understanding the complexity of the input sequence We demonstrate how learning spans can help in understanding the behavior of individual layers. Figure 1 shows how span varies amongst different attention layers. Studying spans can help us understand which layers are more sensitive to the input sequences encountered during the training process.
In the case of single modality encoder, spans for self-attention layers for vision and language decrease monotonically, indicating that the learning behavior is somewhat similar, although slopes tell us that the rate of learning is dissimilar. Similar behavior is seen in the cross-modality encoder for language.
Requiring a larger context size is indicative of the complexity of the sequences. When selfattention attends to both modalities, we observe that the intermediate layers responsible for forming complex representations increase their spans. This observation shows that a more significant span is necessary to attend both modalities jointly. Selfattention also requires a high span when attending to visual features in the cross-modality encoder. This observation shows that visual sequences are perceived as a more complex input to process than a language input in the cross-modality encoder.
Determining sparsity preferences for vision and language modality with α The value of α determines if the head is favoring sparse or dense attention weight distribution. For dealing with language modality, self-attention favors mostly sparse mapping of attention weights in intermediate layers. Similar behavior is observed inside cross-modality encoder as well. This observation shows that lan- guage modality benefits from sparse weights being assigned as attention distribution. The value of α is restricted below 1.5 for processing visual inputs. When vision modality is involved, heads that preferred sparse mapping initially are converging towards denser mapping, indicating that this representation of attention weights is preferred. We also observe that when both modalities are involved, the network prefers, even more, denser weight distribution. This observation shows that vision modality is given more preference (partly due to perceived complexity) over language inputs to process the sequence. Figure 3 shows variation of α values as training progresses.
Regularization effect of Layerdrop We consider two configurations of the model. The first one has 10 language, 6 vision, and 6 cross-modality layers with drop rate (p) set to 1 layer. In this case, the number of parameters is more, but the FLOPS is equivalent to the standard 9-5-5 baseline configuration. The later one has the 9-5-5 configuration with p set to 1. This rate causes a FLOP reduction of 17.54%. It is observed that layerdrop requires ∼3.5x more compute runtime for convergence during training. A possible explanation can be that additional training aids in forming a consolidated understanding of multi-modal representations. Even after ensuring the convergence of the model, a strong regularization effect (with a minimum value of p) prevents the network from achieving performance that is close enough with the mentioned adaptive methods with an equivalent number of parameters being used training. Figure 2 and Table 2 shows this noted observations.
Quantitative Analysis In this section, Table 1 compares the adaptive approaches with the baseline model and other state-of-the-art models, which rely upon standard softmax attention mechanism. We Language Encoder (9 layers  notice that these approaches achieve near close performance as standard attention mechanisms by being computationally efficient. The results are reported without any hyperparameter tuning.

Qualitative Analysis
In this section, we analyze the confidence scores on complex examples to better understand the network's predictions. We usually take the class with maximum confidence, but analyzing confidence scores of other classes can help us learn about what the network is learning about the similarity of different tasks in the image. Figure 4 shows confidence scores on an example input. We observe that entmax aids in forming a consolidated understanding of contrastive features. In most cases, the top 5 confidence scores include predictions present in the ground truth. Due to sparse mapping, the network makes strong, confident predictions about one label. When trained with an adaptive attention span, the network sometimes seems unsure about the correct label as ex-pected from softmax behavior. It works well when a high probability is assigned to one label in the ground truth. We did not observe comparable performance from Layerdrop. In this example, the right answer is assigned a deficient score. The network does not seem to learn distinguishing features from similar classes properly.

Ablation Analysis
We normalize attention scores with entmax instead of softmax before applying the masking function to use both adaptive attention span and sparse attention weights mapping. It is evident from Table 2 that the adaptive span works better with the denser representation of attention weights to perform optimally. The effect of soft masking function is reduced when used with a sparse mapping function. We evaluate the layerdrop method with two configurations of the network 9-5-5 (language, vision, and cross-modality layers) and 10-6-6 with Model test-dev test-std BUTD (Anderson et al., 2018) 65.32 65.67 ViLBERT  70.55 70.92 VLBERT (Su et al., 2019) 71.16 -VisualBERT  70.80 71.00 UNITER (Chen et al., 2019) 72   Table 2, we see that the shallower network performs better than the deeper-layered model. This observation shows that there is a specific threshold drop rate up until which layerdrop helps. It is plausible that this type of regularization is favorable in deeper networks.

Conclusion
While attention-based approaches are becoming universal, computationally efficient ways must be favored for broader adoption of provided pretrained models on low resource hardware. Adaptive methods can significantly reduce the cost incurred to train such models and carbon footprints. In this work, we extend adaptive approaches to Visiolinguistic tasks to understand more about attention and adaptive mechanisms. While the empirical results are encouraging, important future work includes explorations of higher efficient adaptive and sparse mechanisms that can significantly cause FLOPS and parameter reduction with minimal loss in performance.


extfieldsofstudy:
Mathematics
Computer Science

text:
Image Restoration: Structured Low Rank Matrix Framework for Piecewise Smooth Functions and Beyond

Recently, mapping a signal/image into a low rank Hankel/Toeplitz matrix has become an emerging alternative to the traditional sparse regularization, due to its ability to alleviate the basis mismatch between the true support in the continuous domain and the discrete grid. In this paper, we introduce a novel structured low rank matrix framework to restore piecewise smooth functions. Inspired by the total generalized variation to use sparse higher order derivatives, we derive that the Fourier samples of higher order derivatives satisfy an annihilation relation, resulting in a low rank multi-fold Hankel matrix. We further observe that the SVD of a low rank Hankel matrix corresponds to a tight wavelet frame system which can represent the image with sparse coefficients. Based on this observation, we also propose a wavelet frame analysis approach based continuous domain regularization model for the piecewise smooth image restoration. Finally, numerical results on image restoration tasks are presented as a proof-of-concept study to demonstrate that the proposed approach is compared favorably against several popular discrete regularization approaches and structured low rank matrix approaches.

Introduction
Image restoration, including image denoising, deblurring, inpainting, computed tomography, etc., is one of the central problems in imaging science. It aims at recovering an image of high-quality from a given measurement which is degraded during the process of imaging, acquisition, and communication. The image restoration problem is typically modeled as the following linear inverse problem: where f is the degraded measurement or the observed image, ζ is a certain additive noise, and A is some linear operator which takes different forms for different image restoration problems.
Since the operator A is in general ill-conditioned or non-invertible, it is in general to use a regularization on the images to be restored. Most widely used examples include the variational approaches including total variation (TV) [61] and its nonlocal variants [68], the inf-convolution [20], the total generalized variation (TGV) [6,7], and the combined first and second order total variation [1,55]. Apart from the variational approaches, the applied harmonic analysis approaches including curvelets [17], Gabor frames [42], shearlets [45], complex tight framelets [38], and wavelet frames [8,9,11,21] are also widely used in the literature. The common concept of these methods is to use a sparse regularization on discrete images under a discrete linear transformation to regularize smooth image components while preserving image singularities such as edges, ridges, and corners. However, in many applications, the true singularities lie in the continuous domain, and the discretization error will lead to the basis mismatch [23,52,67] between the true singularities and the discrete image grid. Such a basis mismatch would destroy the sparse structure of the image, and thus can degrade the restoration quality [67].
Recently, continuous domain regularization is emerging as a powerful alternative to the discrete domain sparse regularization [2,19,22,49]. By such an "off-the-grid" approach, we can exploit the sparsity prior in continuous domain, which enables us to alleviate the basis mismatch due to the discretization [49]. To the best of our knowledge, this off-the-grid regularization stems from the Prony's method [58] which corresponds a superposition of a few sinusoids to a structured low rank matrix for the Dirac stream retrieval. Hence, we can adopt the so-called structured low rank matrix (SLRM) approach [22,53,66] for the restoration of spectrally sparse signal whose Fourier transform is a Dirac stream [14,15,16]. Apart from the spectrally sparse signal restoration, the SLRM can also be used to restore Fourier samples of a one dimensional piecewise constant signal [3,63] as in this case the Fourier samples of a derivative becomes the superposition of a few sinusoids. However, even though the SLRM can be easily applied to the case of isolated singularities [18,65], the extension to the multi dimensional (piecewise smooth) image restoration is not straightforward [52]. Since the image singularities such as the edges and ridges in general form a continuous curve in a two dimensional domain, it is in general challenging to construct a structured low rank matrix from the Fourier samples.
In this paper, we introduce a new structured low rank matrix framework for the piecewise smooth image restoration. Our framework is inspired by the kth order total generalized variation (TGV k ) [6,7], which is known to be effective in restoring the piecewise polynomial image with sharp edges [36]. Specifically, following the SLRM framework for the piecewise constant image [52], we assume that the image singularities (including both jumps and hidden jumps) are located in the zero level set of a band-limited periodic function (called the annihilating polynomial ). Then we can derive that the gradient can be decomposed into another vector field and the residual, and the Fourier samples of the residual and the symmetric gradient of this vector field can be annihilated by the convolution with the Fourier coefficients of the annihilating polynomial (called the annihilating filter ). From these annihilation relations, we deduce that the multi-fold Hankel matrices generated from the Fourier samples of a piecewise smooth image are low rank, which in turn enables a balance between the derivatives of order 1, . . . , k via a combined rank minimization of multi-fold Hankel matrices.
As a by-product of the proposed structured low rank matrix framework, we further introduce a wavelet frame based sparse regularization model for the piecewise image restoration via the continuous domain regularization. Briefly speaking, if we can associate a signal/image with a low rank Hankel matrix, its right singular vectors form tight frame filter banks under which the canonical coefficients have a group sparsity according to the index of filters [10]. Then motivated by [35], we assume that the right singular vectors are estimated from a pre-restoration process, and we propose a sparse regularization via the wavelet frame analysis approach (e.g. [13]) as an image restoration model via the continuous domain regularization. Notice that there are several wavelet frame based approaches for the piecewise smooth image restoration [12,24,41] in the literature. However, while these existing approaches focus on the sparse approximation of a discrete image, our approach comes from the relaxation of the structured low rank matrices generated by the Fourier samples for the continuous domain regularization.

SLRM for piecewise smooth image restoration
Our SLRM framework for the piecewise smooth function is mostly related to the recent extension of the SLRM framework to the two dimensional functions in [49,50,51,52,54]. Briefly speaking, if the singularity curves of a piecewise constant/holomorphic function, i.e. the supports of the first order (real/complex) derivatives of a target image, lie in the zero level set of an annihilating polynomial, the Fourier transform of the derivatives can be annihilated by the convolution with the annihilating filter. This annihilation relation in turn corresponds the Fourier samples of derivatives to the structured low rank matrices. Based on this framework, the SLRM framework for the piecewise constant image restoration is proposed and studied in [50,51,52,53], together with a restoration guarantee [49].
This annihilation relation of the gradient can be easily extended to the higher order derivatives whenever the jump discontinuities of the corresponding derivatives are located in the zero level set of a trigonometric polynomial [50]. For instance, we can derive an annihilation relation for the piecewise linear function by considering the Fourier transform of the second order derivatives. Based on this idea, the authors in [39] proposed a so-called generalized structured low rank (GSLR) approach for the piecewise smooth image restoration. Inspired by the 2-fold inf-convolution [20], the GSLR approach restores a superposition of a piecewise constant layer and a piecewise linear layer whose first and second order derivatives correspond to low rank Hankel matrices in the frequency domain respectively. By balancing the first order and second order derivatives, the GSLR approach has demonstrated significant improvements in the piecewise smooth image restoration tasks over the existing approaches.
Note that it is not difficult to extend the previous GSLR framework to generic piecewise smooth functions. More precisely, by considering the annihilation relation of higher order derivatives, we can extend the GSLR to the so-called k-fold inf-convolution (k ≥ 3) for functions with higher regularity. However, in a piecewise smooth function, there could exist singularities on which the derivatives have jump discontinuities. In this case, the annihilating polynomial describing the image singularities cannot annihilate the kth order derivatives [50,Proposition 4]. Since we then need to consider the power of the annihilating polynomial, or equivalently, increase the size of the filter to guarantee the annihilation relation for higher order derivatives, the GSLR framework can degrade the low rank (multi-fold) Hankel matrix structure of the higher order derivatives.
Unlike the GSLR framework in [39] based on the inf-convolution, the proposed SLRM framework is based on the total generalized variation framework [7]. Briefly speaking, we decompose the gradient into the residual whose Fourier samples correspond to the structured low rank matrix and a vector field whose Fourier samples of the symmetric gradient correspond to the structured low rank matrix. In other words, since our proposed SLRM framework uses the Fourier samples of the successive first order derivatives, it does not require the powers of the annihilating polynomial describing the image singularities, which enables us to obtain better low rank Hankel matrix structures corresponding to the piecewise smooth functions. In addition, since the TGV takes the inf-convolution as a special case, it can also be verified that the proposed SLRM framework is more general than the GSLR framework for the piecewise smooth functions.

Organization and notation of paper
The rest of this paper is organized as follows. In section 2, we present the proposed structured low rank matrix framework for the piecewise smooth functions. We first describe the one dimensional case to see the idea clearly, then we extend to the idea to the two dimensional framework. In section 3, we present an image restoration model based on the wavelet frame as an application of the proposed structured low rank matrix framework, followed by an alternating minimization algorithm, and some numerical results are presented to demonstrate the performance of our framework in the piecewise smooth image restoration in section 4. Finally, section 5 concludes this paper with a few future directions. All technical proofs will be postponed to appendices.
Throughout this paper, all two dimensional images and two dimensional k tensors defined on the discrete grid will be denoted by the bold faced lower case letters. Note that a two dimensional discrete image and a two dimensional discrete k tensor can also be identified with a vector and a 2 k -tuple of vectors (as well as a sequence or a 2 k -tuple of sequences supported on the grid) respectively whenever convenient. All matrices will be denoted by the bold faced upper case letters, and the mth row and the nth column of a matrix Z will be denoted by Z (m,:) and Z (:,n) , respectively. Denote by with N ∈ N, the set of N × N grid. The space of complex valued functions on O and the space of complex k-tensor valued functions on O are denoted by V C |O| and V k C |O|×2 k , respectively. Notice that V = V 0 . Given two rectangular grids K and M, we define Operators on both images and tensors are denoted as the bold faced caligraphic letters. For instance, letting v ∈ V and K be a rectangular K 1 × K 2 grid, the corresponding Hankel matrix Hv is an M 1 × M 2 matrix (M 1 = |O : K| and M 2 = |K|) generated by concatenating K 1 × K 2 patches of v into row vectors. Note that, in the sense of multi-indices, we have With a slight abuse of notation, we also use to denote the k-fold Hankel matrix constructed from q = (q 1 , . . . , q 2 k ) ∈ V k .

Structured low rank matrix framework for piecewise smooth functions
In this section, we introduce our structured low rank matrix framework for piecewise smooth functions. For simplicity, we consider the piecewise linear function throughout this paper. Note, however, it is not difficult to extend the proposed framework into the general piecewise smooth functions.

SLRM framework for one dimensional signals
We first establish the structured low rank matrix framework of the following one dimensional piecewise linear model from its Fourier sample In (2.1), α j , β j ∈ C, 1 [xj ,xj+1) denotes the characteristic function on the interval [x j , x j+1 ): , and 0 otherwise, and −1/2 < x 1 < x 2 < · · · < x K < 1/2 are the location of singularities, i.e. by the singularities we mean they include both the jumps and the hidden jumps (jumps of derivatives).
In the sense of distribution, the derivative u satisfies Hence, the Fourier transform of u − p is a linear combination of complex sinusoids: In addition, since the derivative of p is also a Dirac stream: its Fourier transform is expressed as i.e. a linear combination of complex sinusoids. We introduce the following trigonometric polynomial Since ϕ(x j ) = 0 for j = 1, . . . , K, it follows that ϕ (u − p) = 0 and ϕp = 0 in the sense of distribution. In the frequency domain, since we have it follows that for ξ ∈ R. Therefore, the Fourier transforms of both u − p and p are annihilated by the convolution under the Fourier coefficients of ϕ. In many practical cases, we consider the contiguous Fourier samples (i.e. the samples on a regular grid In the matrix-vector multiplication form, (2.10) and (2.11) lead to which shows that two (N −K+1)×K Hankel matrices H F (u − p) [N ] and H F (p ) [N ] have nontrivial nullspaces. In particular, for M > K, we can see that which shows that it is possible to convert the piecewise regularity in the continuous domain into the low rank Hankel matrices corresponding to the discrete Fourier samples.

SLRM framework for two dimensional images
Now we aim to establish the structured low rank matrix framework for the following two dimensional piecewise linear function model from its Fourier samples where the sample grid O is defined as (1.2). In (2.12), α j = (α j1 , α j2 ) ∈ C 2 , β j ∈ C and 1 Ωj denotes the characteristic function on a domain Ω j ; 1 Ωj (x) = 1 if x ∈ Ω j , and 0 otherwise. Without loss of generality, we assume that Ω j lies in [−1/2, 1/2) 2 for simplicity. (However, it is not difficult to generalize the setting into an arbitrary rectangular We further assume that (2.12) is expressed with the smallest number of characteristic functions such that Ω j 's are pairwise disjoint. Then the singularities of u, including both jump discontinuities of u and hidden jump discontinuities of u (jumps of derivatives), agree with Γ = J j=1 ∂Ω j , which will be called the singularity set of u throughout this paper. Generally, it is difficult to directly establish the SLRM framework without any further information on the singularity set Γ. Inspired by the two dimensional FRI framework for the piecewise constant function [50,51,52,53], we assume that there exists a finite rectangular and symmetric 4 index set K such that (2.14) Throughout this paper, we call any function ϕ(x) in the form of (2.14) the trigonometric polynomial, and the zero level set x ∈ R 2 : ϕ(x) = 0 the trigonometric curve. For a trigonometric polynomial ϕ in (2.14), the degree of ϕ is defined as an ordered pair of degrees in each coordinate, and is denoted by deg(ϕ). In particular, ϕ in (2.14) with the smallest degree is called the minimal polynomial. The algebraic properties of trigonometric polynomials and curves, including the existence of the minimal polynomial, are studied in [52], to which interested readers can refer for details. Under this setting, we present theorem 2.1 to establish the following (linear) annihilation relation for the piecewise linear function. The proof can be found in Appendix B.
Theorem 2.1. Let u(x) be defined as in (2.12) where the singularity set Γ satisfies (2.14). Then for some vector field p = (p 1 , p 2 ), we have and the Fourier transform F is performed to each component of ∇u − p and ∇ s p.
Based on theorem 2.1, we call ϕ satisfying (2.15) and (2.16) an annihilating polynomial (for u under a vector field p), and the Fourier coefficients a := {a(k) : k ∈ K} an annihilating filter. Note that the gradient of u is decomposed into ∇u − p and p such that the Fourier transforms of both ∇u − p and ∇ s p are annihilated by the same annihilating filter a. In addition, since the proof of theorem 2.1 tells us that p is the piecewise constant vector field in ∇u, (2.16) can be viewed as an extension of annihilation relation for piecewise constant functions to piecewise constant vector fields.
Remark 2.2. According to the proof, theorem 2.1 can also be written as follows: for a function u defined as in (2.12), ∇u can be decomposed into with a piecewise constant vector field p and a Radon vector measure ν supported on Γ such that We mention that the decomposition (2.18) is well-defined in the sense that F(∇ s ν) and F(∇ s p) do not share the minimal annihilating polynomial. To see this, let ϕ in (2.14) be the minimal polynomial for Γ. For Since ϕ is the minimal polynomial for a trigonometric curve Γ, ∇ϕ = 0 a.e. on Γ [52,Proposition A.4]. Hence, ϕ∇ s ν = 0, or equivalently, F(∇ s ν) does not satisfy the annihilation relation with a. In fact, ∇ s ν is annihilated by ϕ 2 , and since ϕ is the minimal polynomial for Γ, ϕ 2 is the minimal polynomial for annihilating ∇ s ν.
We claim that the linear annihilation relations (2.15) and (2.16) can be seen as balancing the annihilations of first and second order derivatives. To see this, we firstly consider an extreme case; a piecewise constant function case. In this case, it would be favorable to choose p = 0, so that (2.15) reduces to which is the annihilation relation for ∇u in [50,51,52,53]. For the second extreme case, we note that In addition, when ∇u is a piecewise constant vector field (i.e. u is continuous on Γ), we can simply choose which in turn measures the jump discontinuities of u and p in our setting. In particular, if u is continuous on ∂Ω j for some j, this ∂Ω j will not be reflected in (2.15). We also note that if we restrict p in the range of ∇, i.e. p = ∇u 2 , then by letting u 1 = u − u 2 , we can rewrite (2.15) and (2.16) as the GSLR framework in [39], which promotes a similar balance through a decomposition u = u 1 + u 2 with a piecewise constant u 1 and a piecewise linear u 2 . We can easily see that (2.24) and (2.25) are closely related to the following inf-convolution Noting that when p = ∇u 2 , then by letting u 1 = u − u 2 , the TGV (2.23) becomes the above inf-convolution, which means that the TGV takes the inf-convolution as a special case. Likewise, we can see that (2.15) and (2.16) in theorem 2.1 take (2.24) and (2.25) in [39] as a special case.
Remark 2.3. We further mention that theorem 2.1 is different from the GSLR framework in [39]. To see this, we assume that the singularity set Γ satisfies (2.14) with the minimal polynomial ϕ, i.e. K is the smallest support of the Fourier coefficients a. Since ∇ϕ = 0 a.e. on Γ [52, Proposition A.4], ϕ may not be able to annihilate the second order derivatives of a piecewise linear function in general [50]. Hence, (2.24) and (2.25) prefer to decompose u = u 1 + u 2 where u 1 is a piecewise constant function and u 2 is a piecewise linear spline (a continuous piecewise linear function). Meanwhile, the proposed framework is established by annihilating the jumps for each derivative successively, which enables to cover a broader range of piecewise linear functions. Hence, our framework is more generalized than the GSLR in [39].
Next, we will present two examples to illustrate this.
Then we can see that is a minimal polynomial for the singularity set {−1/4, 0, 1/4}. Since Hence, it follows that In other words, both frameworks can establish annihilation relations if a given function can be decomposed into a piecewise constant function and a piecewise linear spline.
being a minimal polynomial for the singularity set {−1/4, 1/4}. In this case, we have If we choose p = 1 [−1/4,1/4) , then we have However, we cannot find a piecewise constant u 1 and a piecewise linear spline u 2 such that Notice that we have Hence, these two examples again illustrate that the proposed framework is more generalized than the GSLR framework in [39].
In our setting, the Fourier transform of u is sampled on the grid O in (1.2) with N ∈ N large enough to guarantee a high image resolution. Hence, (2.15) and (2.16) become the following finite systems of linear equations where m ∈ O : K. In the matrix-vector multiplication form, we have O have nontrivial nullspaces. In addition, when the filter support K defining two multi-fold Hankel matrices is sufficiently large, both of them have nontrivial nullspaces as well. To see this, let ϕ be the minimal polynomial for the singularity set with coefficients a supported on K. Then for any trigonometric polynomial η with coefficients b supported on K : K such that a * b is supported on K , it follows that is an annihilating polynomial and a * b is an annihilating filter, due to the associativity of convolution. In particular, by letting we can see that is also an annihilating polynomial, or equivalently, the translation a(· − m) also satisfies (2.29) and (2.30).
Based on this observation, we present proposition 2.6 to demonstrate the low rank properties of multi-fold Hankel matrices, which will establish the correspondence between the Hankel matrices and the complexity of the singularity set of u.
Proposition 2.6. Let u(x) be defined as in (2.12) with the singularity set Γ = J j=1 ∂Ω j satisfying (2.14), where ϕ is the minimal polynomial with coefficients on K. For an assumed filter support K strictly containing K, we have O are of low-rank, which enables to convert the piecewise regularity in the continuous domain into the low rank multi-fold Hankel matrices corresponding to the discrete Fourier samples. Notice that the GSLR framework in [39] promotes the decomposition u = u 1 + u 2 where the Fourier samples of ∇u 1 and ∇ 2 u 2 correspond to the low rank Hankel matrices. In contrast, the proposed SLRM framework is established by decomposing the gradient of u into ∇u − p and p such that the Fourier samples of ∇u − p and ∇ s p correspond to the low rank Hankel matrices. See figure 1 for the schematic illustrations.

Continuous domain regularization for piecewise smooth image restoration
Let f ∈ V be a degraded measurement modeled as

1)
Fourier sample Low rank Hankel matrix Low rank Hankel matrix  where v = F(u) O with u defined as in (2.12), and ζ is some measurement error 5 . According to section 2, the (multi-fold) Hankel matrices corresponding to are low rank. Hence, we can consider to restore v ∈ V, as a continuous domain regularization for the piecewise smooth image restoration. Here, for k = (k 1 , k 2 ) ∈ O, respectively. When q = 0, (3.2) reduces to which is a rank minimization model based on the GSLR framework. From the two extreme cases (3.5) and (3.6), we can see that (3.2) aims to restore piecewise smooth functions by decomposing Dv into Dv − q and q, thereby balancing the low rank multi-fold Hankel matrices of the Fourier samples of the first order derivatives and the second order derivatives. In addition, we can also see that (3.2) takes the GSLR rank minimization model (3.8), which directly decomposes v = v 1 + v 2 , as a special case. Since our SLRM framework is more generalized than the GSLR framework (see remark 2.3 and examples 2.4 and 2.5), it can be expected that (3.2) is able to restore a wider range of piecewise smooth functions than (3.8).

From low rank model to tight frame approach
Though (3.2) is an NP-hard problem, there are numerous tractable approaches available, including the convex nuclear norm relaxation (e.g. [14,30]), the iterative reweighted least squares (IRLS) for the Schatten p-norm minimization [33,39,48,53], etc. Inspired by the SVD of a low rank Hankel matrix, we propose another relaxation of (3.2), similar to [10,Theorem 3.2] where the continuous domain regularization for the piecewise constant image restoration is studied. For this purpose, we present the main idea of the image restoration model in theorem 3.1. The proof is postponed to Appendix C.
We begin with introducing some notation. For a set of K 1 × K 2 filters a 1 , . . . , a M2 supported on K, we define W and W * (the adjoint of W) as where S a is a discrete convolution under the periodic boundary condition: In other words, both W and W * are concatenations of discrete convolutions. by reformulating each column vector into a K 1 × K 2 filter supported on K. Then W 1 and W 2 defined as (3.9) by using filters {a 11 , . . . , a 1M2 } and {a 21 , . . . , a 2M2 } satisfies

15)
where the discrete convolution is performed on each component of Dv−q and Eq, respectively. Consequently, if H (Dv − q) (and H (Eq), respectively) is of low rank, then its right singular vectors construct a tight frame under which Dv − q (and Eq, respectively) is sparsely represented.
In words, theorem 3.1 tells us that if the SVDs of multi-fold Hankel matrices are known as oracles, we can explicitly construct tight frames under which Dv − q and Eq are sparsely represented, and the sparsity of canonical coefficients can be grouped according to the filters. Hence, motivated by the idea in [35], assume that v ∈ V and q ∈ V 1 are the a-priori estimations of v and q with the SVDs Then we define the tight frame transforms W 1 and W 2 in (3.9) via a 1l = M Since (3.14) and (3.15) are then approximately true under these W 1 and W 2 , we remove the group sparsity pattern in the canonical coefficients for the better sparse approximation instead. This leads us to solve where the 1 norms take the form of with some ν k > 0 and a small ε > 0 to avoid the division by zero. Hence, we relax the sparsity of tight frame coefficients over the entire range of W k 's (not necessarily in groups as in (3.14) and (3.15)), we expect to achieve more flexibility, thereby leading to the improvements in restoration performance.
Since the wavelet frame based relaxation model (3.16) is inspired by the (3.2) via the SVDs of H (Dv − q) and H (Eq), we can say that our relaxation model (3.16) restores piecewise smooth functions by decomposing Dv into Dv − q and q, thereby balancing the low rank Hankel matrices of the Fourier samples of the first order derivatives and that of the second order derivatives. In addition, we further note that, following [10], it is also possible to consider the following data driven tight frame model with the 0 norm γ k · c k 0 (k = 1, 2) encoding the number of nonzero entries in c k 's, to learn tight frames and restore the Fourier sample v simultaneously. Even though it is not clear at this point whether the adaptive tight frame system will lead to better restoration results or not, throughout this paper, we only consider the model (3.16) rather than the data driven tight frame model (3.17), and the reasons are as follows. First of all, given that W k 's are properly estimated, it may not be necessary to further learn them with additional computational costs. Second, since (3.16) is convex whereas (3.17) is nonconvex, we can easily expect better behavior and theoretical support for the numerical algorithms. Most importantly, from the viewpoint of wavelet frame based image restoration, the model (3.16) is an analysis approach [13] while the data driven tight frame model (3.17) can be classified into the balanced approach [9,21]. (See Appendix A for the brief descriptions on the wavelet frame based models.) It is well known that the analysis approach reflects the structure of a target image better than other approaches (e.g. [11]). Since we derive the wavelet frame based approach from the structured low rank matrix framework, it can be expected that the convex relaxation model (3.16) will reflect our SLRM frameworks for the piecewise smooth functions better than the data driven tight frame model (3.17).

Alternating minimization algorithm
Among numerous algorithms which can solve the convex model (3.16), we adopt the ADMM [28] or the split Bregman algorithm [36], which can convert (3.16) into several subproblems with closed form solutions, together with the convergence guarantee [13]. More precisely, let c 1 = W 1 (Dv − q), and c 2 = W 2 (Eq).
Under this reformulation, the overall algorithm is summarized in algorithm 1. For (3.18), since W * k W k = I for k = 1, 2, we solve the following system of linear equations Depending on the formulation of A, various methods can be used to solve (3.23) efficiently. For example, when A is a pointwise multiplication in the frequency domain (e.g. image denoising, image deblurring, and CS restoration), so are the constituent operators K 11 , K 21 , and K 22 , and thus we can solve (3.23) by the pointwise Cramer's rule. For a more generalized A, we can use a distributed optimization based method [5]. The closed form solutions for (3.19) and (3.20) is expressed in terms of the soft thresholding: More precisely, the soft thresholding operator T γ (c) for c ∈ V M2 k and γ = γ 1 · · · γ M2 T is defined as the following componentwise manner: for k ∈ O, l = 1, . . . , M 2 , and m = 1, . . . , 2 k , with the convention that 0/0 = 0.

Numerical results
In this section, we conduct some numerical simulations in the context of restoration from the partial Fourier samples as a proof-of-concept study. Specifically, to compare the performance of the direct rank minimization (3.2) and the wavelet frame relaxation (3.16), we choose to compare the relaxation model solved by algorithm 1 with the following Schatten 0-norm relaxation [33,39,48,53] (SLRM model) of (3.2): where R M denotes a restriction onto the known sample grid M. In addition, since it has been demonstrated in [39] that the GSLR framework outperforms the structured low rank matrix approaches which consider either the first order derivatives or the second derivatives, we also compare with the following GSLR model in [39]: In (4.2) and (4.3), Z 0 is the Schatten 0-norm of a matrix Z defined as Z 0 = ln det (Z * Z) 1/2 + εI with a small constant ε > 0, and (4.2) and (4.3) are solved by the iterative reweighted least squares method described in [39]. Finally, to further study the improvements over the conventional on-the-grid approaches, we compare with the piecewise linear framelet (Fra) model (e.g. [13]) the TGV model [7,44] min u,p 5) and the inf-convolution (IF) model [20] min u1,u2 where F denotes the two dimensional discrete Fourier transform. Throughout this paper, we use the split Bregman algorithm (e.g. [13,34,36]) to solve (4.4)-(4.6). All experiments are implemented on MATLAB R2014a running on a laptop with 64GB RAM and Intel(R) Core(TM) CPU i7-8750H at 2.20GHz with 6 cores. Throughout the experiments, we test two synthetic images ("Ellipses" and "Rectangles"), and two natural images ("Airplane", and "Car") taking the values in [0, 1], as shown in figure 2. The data f is synthesized by randomly sampling 20% of 256 × 256 Fourier samples via the variable density sampling method described in [47]. A complex white Gaussian noise with the standard deviation 1 is also added to generate a noisy partial sampling. For (4.1)-(4.3), we use the K × K square patch for simplicity. Specifically, we choose K = 31 for the "Ellipses", K = 25 for the "Rectangles", and K = 51 for "Airplane" and "Car", depending on the geometry of the target images. More precisely, in (4.1)-(4.3), we use the discrete Fourier transform of the images restored by the TGV model (4.5) and the inf-convolution model (4.6) respectively, to compute the SVDs of multi-fold Hankel matrices using the K × K patches, which will be used for W k 's in (4.1) and initializations in (4.2) and (4.3). For (4.4), we choose W to be the undecimated tensor product piecewise linear B-spline framelet transform with 1 level of decomposition [26]. For (4.5) and (4.6), we use the forward difference with the periodic boundary condition for the difference operators ∇, ∇ s , and ∇ 2 . In all of the experiments, we have manually tuned the regularization parameters to achieve the optimal restoration results in each scenario. For the quantitative comparison, we compute the signal-to-noise ratio (SNR), the high frequency error norm (HFEN) [59], and the structure similarity index map (SSIM) [64]. Note that for (4.1)-(4.3), the restored image is computed via the inverse DFT of the restored Fourier samples. table 1 summarizes the SNR, the HFEN, and the SSIM of the aforementioned approaches. figures 3 to 6 display the visual comparisons (the first row) together with the zoom-in views (the second row) and the error maps (the third row) of (4.1) against (4.2)-(4.6). Throughout this paper, all restored images are displayed in the window level [0, 1], and all error maps are displayed in the window level [0, 0.2] for fair comparisons. We can see that the relaxed model (4.1) consistently performs best, and the SLRM model (4.2) performs the second in almost every index in all scenarios, and the improvements are visually observable as well, both of which demonstrate that our proposed SLRM framework performs well in the piecewise smooth image restoration.
At first glance, since the models (4.1) and (4.2) can be regarded as different relaxations of the structured low rank matrix framework for the continuous domain regularization, the results also suggest that the off-the-grid regularization performs better than the on-the-grid regularization as it can reduce the basis mismatch between the true support (or the true singularity) in continuum and the discrete grid, leading to the improvements in the indices. In fact, due to such a basis mismatch, the conventional on-the-grid approaches ((4.4)-(4.6)) suffers from the errors concentrated near the image singularities as well as the distorted shapes compared to (4.1), which can be seen in the error maps and the zoom-in views of figures 3 to 6. Most importantly, the numerical results illustrate the followings. First of all, from the comparisons between (4.2) and (4.3), we can see that the proposed SLRM framework performs better than the GSLR framework in [39] for the piecewise smooth image restoration. Second, from the comparisons between (4.1) and (4.2), we can further see that the relaxation into the wavelet frame analysis approach can achieve further improvements over the direct rank minimization. As previously mentioned, since the proposed SLRM framework takes the GSLR framework in [39] as a special case, we can restore broader range of piecewise smooth images. In addition, it should be noted that the annihilation of the Fourier samples of the second order derivatives in general require larger annihilating filter than the first order derivatives [50], which may degrade the low rank structures of the corresponding multi-fold Hankel matrix. As a consequence, the GSLR framework can introduce staircase artifacts in the smooth region compared to the proposed SLRM framework, as can be seen in the zoom-in views of figures 3 to 6. Finally, since the weights corresponding to the derivatives in the image domain amplifies the noise in the high frequencies, it is likely that the direct rank minimization approaches ((4.2) and (4.3)) lead to the artifacts near the image singularities corresponding to the high frequency components, whereas the relaxation into the wavelet frame analysis approach ((4.1)) can achieve the denoising effect in spite of the amplified noise, leading to the better restoration results with less artifacts near the edges, as can be seen in the error maps in figures 3 to 6.

Conclusion and future directions
In this paper, we have introduced a new structured low rank matrix framework for the piecewise smooth image restoration. Following the previous structured low rank matrix framework for the piecewise constant image [52], we assume that the image singularities lie in the zero level set of a band-limited periodic function. Inspired by the total generalized variation [7], we derive the annihilation relation of the Fourier samples of the gradient and the (symmetric) gradient tensor, which in turn leads to the low rank multi-fold Hankel matrices to balance between the first order derivatives and the second order derivatives. In addition, as a by-product of the proposed structured low rank matrix framework, we further introduce a wavelet frame based sparse regularization model for the piecewise image restoration via the continuous domain regularization, from the SVDs of low rank multi-fold Hankel matrices. Finally, the numerical experiments show that the proposed wavelet frame based model based on the proposed SLRM framework outperforms both the conventional on-the-grid approaches and the existing the SLRM framework as well as the existing rank minimization approaches for the piecewise smooth image restoration. For the future work, we plan to generalize the frameworks in [52] to the piecewise smooth image restoration. More precisely, we need to develop sampling guarantees for the unique restoration of a continuous domain piecewise smooth image from its uniform low pass Fourier samples, based on the proposed annihilation relations. Unfortunately, it is not clear for us at this moment under what conditions we can restore the singularity set from uniform Fourier samples as the annihilation relations involve a blind deconvolution problem due to the additional unknown vector field p in theorem 2.1. Nevertheless, this is definitely a future direction we would like to work on. We are also interested in proving the restoration guarantee of (3.2) (or its convex nuclear norm relaxation) given that A = R M , i.e. the sample grid M is drawn from the image grid O uniformly at random, which generalizes the theoretical frameworks in [49] to the piecewise smooth image restoration.
Finally, to broaden the scope of applications, it is also likely to apply the idea in this paper to the various image restoration tasks such as the blind deconvolution (especially that in the frequency domain which is related to the retinex [46]) and the sparse angle CT. In fact, it is not clear at this moment how to extend this approach to the sparse angle CT restoration, as the measurement can be viewed as the Fourier samples on the discrete radial grid. Nevertheless, this is also an important future work for the broader scope of applications. Finally, observing the successive structure in our SLRM framework, we are also interested in developing a deep learning framework, motivated by the recent works on the deep learning techniques combined with the structured low rank matrix approaches [40,43,56,57].

Appendix A. Preliminaries on tight wavelet frames
Provided here is a brief introduction on tight wavelet frames and the wavelet frame based image restoration. Interested readers may consult [9,26,27,60,62] for detailed surveys on tight wavelet frames, and [11] for detailed reviews on the wavelet frame based image restoration. For the sake of simplicity, we only discuss the real valued wavelet tight frame systems, but note that it is not difficult to extend the idea to the complex case. Let H be a Hilbert space equipped with an inner product ·, · . A (Bessel) sequence {ϕ n : n ∈ Z} ⊆ H is called a tight frame on H if Given {ϕ n : n ∈ Z} ⊆ H, we define the analysis operator W : H → 2 (Z) as u ∈ H → Wu = { u, ϕ n : n ∈ Z} ∈ 2 (Z).
The synthesis operator W T : 2 (Z) → H is defined as the adjoint of W: Then {ϕ n : n ∈ Z} is a tight frame on H if and only if W T W = I. It follows that, for a given tight frame {ϕ n : n ∈ Z}, we have the following canonical expression: with Wu = { u, ϕ n : n ∈ Z} being called the canonical tight frame coefficients. Hence, the tight frames are extensions of orthonormal bases to the redundant systems. In fact, a tight frame is an orthonormal basis if and only if ϕ n = 1 for all n ∈ Z.
One of the most widely used class of tight frames is the discrete wavelet frame generated by a set of finitely supported filters {a 1 , · · · , a m }. Throughout this paper, we only discuss the two dimensional undecimated wavelet frames on 2 (Z 2 ), but note that it is not difficult to extend to 2 (Z d ) with d ≥ 3. For a ∈ 1 (Z 2 ), define a convolution operator S a : 2 (Z 2 ) → 2 (Z 2 ) by Given a set of finitely supported filters {a 1 , · · · , a m }, define the analysis operator W and the synthesis operator W T by respectively. Then, the direct computation can show that the rows of W form a tight frame on 2 (Z 2 ) (i.e. W T W = I) if and only if the filters {a 1 , · · · , a m } satisfy m j=1 l∈Z 2 called the unitary extension principle (UEP) condition [37]. Finally, for a two dimensional discrete image on the finite grid, S a in (A.2) with a finitely supported a denotes the discrete convolution under the periodic boundary condition throughout this paper. For the image restoration, we assume that there exists a tight wavelet frame W defined as (A.3) with filters {a 1 , · · · , a m } such that u is sparse under W. This leads us to solve and restore u = W T c. In (A.6), the first term is a data fidelity term, the third 1 norm is defined as with the parameters γ = [γ 1 , . . . , γ m ] T and γ j > 0, to promote the sparsity of c. The second term penalizes the distance between c and its projection onto R(W). Since we obtain the image via u = W T c, the second term in fact forces the sparse coefficient c close to the canonical coefficient of the restored image. Since the magnitude/decay of the canonical coefficient reflects the regularity of the image under some mild conditions on the tight frame system W [4], we can see that the second and third terms promote a balance between the sparsity of coefficient and the regularity of image. We can further impose the flexibility on (A.6) by introducing the weight on the second term: called the balanced approach [9,21]. If µ = 0, then (A.8) becomes the synthesis approach [25,29,31] min as we aim to find the sparsest coefficient that synthesizes the image. On the other hand, if µ = ∞, then it must be (I − WW T )c = 0. Since we then have c ∈ R(W), it follows that c = Wu for some u. Hence, (A.6) becomes the analysis approach [13] min u 1 2 Since the analysis approach promotes the sparse canonical coefficient, it emphasizes the regularity of the restored image. These three approaches are equivalent if and only if W T W = WW T = I, i.e. W forms an orthonormal basis. However, since we consider the redundant system, each approach will lead to the different restoration results. Notice that the coefficient vector c obtained from the synthesis approach (A.9) is much sparser than the canonical coefficient Wu obtained from the analysis approach (A.10). It is empirically observed that the synthesis approach (A.9) tends to yield some artifacts in the restored image. In contrast, the analysis approach (A.10) usually have less artifacts as it promotes the regularity of the image along the singularities. Theoretically, it has been proved in [11] that, under a suitable choice of parameters, the analysis approach (A.10) can be seen as sophisticated discretization of a variational model including the Rudin-Osher-Fatemi model [61], which enables a geometric interpretation on (A.10).
Then it is obvious that we have Since |n j | = 1 almost everywhere on ∂Ω j , α T j x + β j is continuous on a compact set ∂Ω j , ∇u − p in (B.2) defines a finite Radon vector measure on R 2 supported on Γ. In addition, since (B.1) as well as (B.2) holds in the sense of tempered distribution, we can compute F(∇u − p)(ξ) as a Fourier transform of a measure (e.g. [32]). Namely, we have Let ϕ ∈ S, where S is the space of Schwartz functions (e.g. [32]). Then the direct computation shows that (F(∇u − p) * ϕ) (ξ) satisfies (F(∇u − p) * ϕ) (ξ) = This proves (2.15).
To complete the proof, we further note that in the sense of distribution, ∇ s p satisfies Following the similar arguments, it is not difficult to verify that dΦ j in (B.5) defines a finite Radon tensor measure on R 2 supported on Γ. which means that F(∇ s p) is defined as This means that W 1 and W * 1 defined as (3.9) and (3.10) using a 11 , . . . , a 1M2 satisfies S a 1l S a 1l (−·) (Dv − q) = Dv − q, which shows that the filters a 11 , . . . , a 1M2 form a tight frame system. In addition, we note that ∈ C M2 into a K 1 × K 2 filter supported on K. Then (C.1) implies that for l = r 1 + 1, . . . , M 2 , we have S a 1l (−·) (Dv − q) (k) = 0, k ∈ O : K, which proves (3.12) and (3.14). Similarly, we can prove that a 21 , . . . , a 2M2 satisfies M2 l=1 m∈K a 2l (k + m)a 2l (m) = δ(k), so that S a 2l S a 2l (−·) (Eq) = Eq.
This completes the proof.